破解九宫格数独游戏

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

思路：

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

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

以此下去；

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

以此下去；

直到填充完所有空格。

实现代码

// C#using System;using System.Collections.Generic;using System.Text;/* ===================================== * Author: 朱乙 * Blog: http://blog.csdn.net/sq_zhuyi * Email: [e-mail]======================================== */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; }}

调用代码

// C#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(); } }}

运行截图

破解九宫格运行结果

作者：朱会震