數(shù)獨(dú)是一種比較費(fèi)時(shí)費(fèi)腦的游戲蝇闭，一般難度的數(shù)獨(dú)玩下來(lái)也得1個(gè)小時(shí)左右呻率，本人是偽數(shù)獨(dú)愛(ài)好者硬毕，碰到難點(diǎn)的數(shù)獨(dú)需要花上若干個(gè)小時(shí)，于是偷懶寫了一套破解程序礼仗，特拿出來(lái)分享吐咳，希望有人喜歡。
思路：
- 從第一個(gè)空格開(kāi)始元践，計(jì)算出所有可能填充的數(shù)字韭脊，拿出第一個(gè)進(jìn)行填充，將剩下的可能數(shù)字記錄下來(lái)单旁；
- 接著計(jì)算下一個(gè)空格所有可能的數(shù)字（在前邊填充上的基礎(chǔ)上）沪羔，拿出第一個(gè)可能進(jìn)行填充，將剩下的記錄象浑；
- 以此下去蔫饰；
- 直到出現(xiàn)這樣一個(gè)空格：所有的數(shù)字都沒(méi)法填充（有沖突），就回到最后一次那個(gè)假設(shè)點(diǎn)愉豺，重新嘗試其它的可能數(shù)字篓吁；
- 以此下去；
- 直到填充完所有空格蚪拦。
實(shí)現(xiàn)代碼
// C#
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;//存儲(chǔ)數(shù)獨(dú)數(shù)字
public SudokuService(string numStr)
{
string s = numStr.Replace(",", "");
if (s.Length != 81)
{
throw new Exception("初始數(shù)獨(dú)錯(cuò)誤杖剪，必須是81個(gè)數(shù)字");
}
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("初始數(shù)獨(dú)錯(cuò)誤冻押，必須是81個(gè)數(shù)字");
}
pArr = GetArray(numArr);
}
/// <summary>
/// 獲取結(jié)果
/// </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>
/// 打印結(jié)果
/// </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;
}
}
}
}
}
}
}
//記錄每個(gè)位置的可能數(shù)字
private List<PosValues> posVals = new List<PosValues>();
//獲取當(dāng)前位置的可能數(shù)字
private PosValues GetNumber(int[] pos)
{
List<int> nums = new List<int>();
for (int n = 1; n <= 9; n++)
{
nums.Add(n);
}
//3宮格內(nèi)
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;
}
}
調(diào)用代碼
// 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("計(jì)算結(jié)束，用時(shí) {0} 毫秒", span.Milliseconds);
Console.WriteLine("press enter to exit");
Console.ReadLine();
}
}
}
運(yùn)行截圖
破解九宮格運(yùn)行結(jié)果
作者：朱會(huì)震
