【开源】完美破解九宫格（数独）游戏

数独是一种比较费时费脑的游戏，一般难度的数独玩下来也得1个小时左右，本人是伪数独爱好者，碰到难点的数独需要花上若干个小时，于是偷懒写了一套破解程序，特拿出来分享，希望有人喜欢。

思路：

1、从第一个空格开始，计算出所有可能填充的数字，拿出第一个进行填充，将剩下的可能数字记录下来；

2、接着计算下一个空格所有可能的数字（在前边填充上的基础上），拿出第一个可能进行填充，将剩下的记录；

3、以此下去；

4、直到出现这样一个空格：所有的数字都没法填充（有冲突），就回到最后一次那个假设点，重新尝试其它的可能数字；

5、以此下去；

6、直到填充完所有空格。

实现代码：

using System;
using System.Collections.Generic;
using System.Text;
/* =====================================* Author: 朱乙* Blog: http://blog.csdn.net/sq_zhuyi* Email: sqzhuyi@gmail.com
======================================== */
namespace SudokuResponder
{public class SudokuService{Number[][][][] pArr = null;//存储数独数字public SudokuService(string numStr){string s = numStr.Replace(",", "");if (s.Length != 81){throw new Exception("初始数独错误，必须是81个数字");}int[] numArr = new int[81];for (int i = 0; i < s.Length; i++){numArr[i] = Convert.ToInt32(s[i].ToString());}pArr = GetArray(numArr);}public SudokuService(int[] numArr){if (numArr.Length != 81){throw new Exception("初始数独错误，必须是81个数字");}pArr = GetArray(numArr);}/// <summary>/// 获取结果/// </summary>/// <returns></returns>public string GetResult(){FillArray();StringBuilder sb = new StringBuilder();for (int m = 0; m < 3; m++){for (int i = 0; i < 3; i++){for (int n = 0; n < 3; n++){for (int j = 0; j < 3; j++){sb.Append(pArr[m][n][i][j].Value);}}sb.Append(",");}}return sb.ToString().TrimEnd(',');}/// <summary>/// 打印结果/// </summary>public void PrintResult(){for (int m = 0; m < 3; m++){if (m == 0) Console.WriteLine("".PadLeft(25, '-'));for (int i = 0; i < 3; i++){for (int n = 0; n < 3; n++){if (n == 0) Console.Write("| ");for (int j = 0; j < 3; j++){var pv = pArr[m][n][i][j];if (pv.Default) Console.ForegroundColor = ConsoleColor.Red;Console.Write("{0} ", pv.Value);Console.ForegroundColor = ConsoleColor.White;}Console.Write("| ");}Console.WriteLine();}Console.WriteLine("".PadLeft(25, '-'));}}private Number[][][][] GetArray(int[] defVal){Number[][][][] pArr = new Number[3][][][];for (int m = 0; m < 3; m++){pArr[m] = new Number[3][][];for (int n = 0; n < 3; n++){pArr[m][n] = new Number[3][];for (int i = 0; i < 3; i++){pArr[m][n][i] = new Number[3];for (int j = 0; j < 3; j++){pArr[m][n][i][j] = new Number() { Value = 0, Default = false };}}}}int c = 0;for (int m = 0; m < 3; m++){for (int i = 0; i < 3; i++){for (int n = 0; n < 3; n++){for (int j = 0; j < 3; j++){int val = defVal[c++];pArr[m][n][i][j].Value = val;if (val > 0)pArr[m][n][i][j].Default = true;}}}}return pArr;}private void FillArray(){for (int m = 0; m < 3; m++){for (int n = 0; n < 3; n++){for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){if (pArr[m][n][i][j].Default == false){//空白格var pv = GetNumber(new int[4] { m, n, i, j });if (!pv.Ok){m = pv.Position[0];n = pv.Position[1];i = pv.Position[2];j = pv.Position[3];ClearAfter(pv.Position);}pArr[m][n][i][j].Value = pv.Value;}}}//end small}}//end big}//清空该位置后边的空格private void ClearAfter(int[] pos){int min = pos[0] * 1000 + pos[1] * 100 + pos[2] * 10 + pos[3];for (int m = 0; m < 3; m++){for (int n = 0; n < 3; n++){for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){if (m * 1000 + n * 100 + i * 10 + j > min){if (pArr[m][n][i][j].Default == false){pArr[m][n][i][j].Value = 0;}}}}}}}//记录每个位置的可能数字private List<PosValues> posVals = new List<PosValues>();//获取当前位置的可能数字private PosValues GetNumber(int[] pos){List<int> nums = new List<int>();for (int n = 1; n <= 9; n++){nums.Add(n);}//3宫格内for (int i = 0; i < 3; i++){for (int j = 0; j < 3; j++){int a = pArr[pos[0]][pos[1]][i][j].Value;if (a > 0 && nums.Contains(a)){nums.Remove(a);}}}//横向for (int n = 0; n < 3; n++){for (int j = 0; j < 3; j++){int a = pArr[pos[0]][n][pos[2]][j].Value;if (a > 0 && nums.Contains(a)){nums.Remove(a);}}}//纵向for (int m = 0; m < 3; m++){for (int i = 0; i < 3; i++){int a = pArr[m][pos[1]][i][pos[3]].Value;if (a > 0 && nums.Contains(a)){nums.Remove(a);}}}if (nums.Count == 0){if (posVals.Count == 0){return new PosValues(){Value = 0};}var pv = posVals[posVals.Count - 1];pv.Ok = false;pv.Value = pv.Values[0];pv.Values.Remove(pv.Value);if (pv.Values.Count == 0){posVals.Remove(pv);}return pv;}else{var pv = new PosValues();pv.Position = pos;pv.Value = nums[0];nums.Remove(pv.Value);pv.Values = nums;if (nums.Count > 0){posVals.Add(pv);}return pv;}}}public struct Number{public int Value;public bool Default;}public class PosValues{public int[] Position;public List<int> Values;public bool Ok = true;public int Value;}
}

调用代码：

using System;
using System.Collections.Generic;namespace SudokuResponder
{class Program{static void Main(string[] args){string s = "000000007,008000400,003801600,804306201,000000000,105407908,007603800,006000100,400000005";SudokuService service = new SudokuService(s);DateTime start = DateTime.Now;string result = service.GetResult();TimeSpan span = DateTime.Now - start;service.PrintResult();Console.WriteLine("计算结束，用时 {0} 毫秒", span.Milliseconds);Console.WriteLine("press enter to exit");Console.ReadLine();}}
}

运行截图：