C# 數(shù)獨求解算法的實現(xiàn)
更新時間：2020年01月20日 10:18:31 作者：coredx
這篇文章主要介紹了C# 數(shù)獨求解算法的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
前言
數(shù)獨是一種有趣的智力游戲，但是部分高難度數(shù)獨在求解過程中經(jīng)常出現(xiàn)大量單元格有多個候選數(shù)字可以填入，不得不嘗試填寫某個數(shù)字然后繼續(xù)推導(dǎo)的方法。不幸的是這種方法經(jīng)常出現(xiàn)填到一半才發(fā)現(xiàn)有單元格無數(shù)可填，說明之前就有單元格填錯了把后面的路堵死了。這時就需要悔步，之前的單元格換個數(shù)重新試。然而更坑的是究竟要悔多少步呢？不知道。要換數(shù)字的時候該換哪個呢？也不知道。手算時就需要大量草稿紙記錄填寫情況，不然容易忘了哪些試過哪些沒試過。
在朋友那里玩他手機上的數(shù)獨的時候就發(fā)現(xiàn)這個問題很煩，到這里其實就不是一個智力游戲，而是體力游戲了。這種體力活實際上交給電腦才是王道。網(wǎng)上搜了一圈，大多都是Java、vb、C++之類的實現(xiàn)，且多是遞歸算法。遞歸有一個問題，隨著問題規(guī)模的擴大，很容易不小心就把棧撐爆，而且大多數(shù)實現(xiàn)只是求出答案就完了，很多求解中的信息就沒了，而我更想看看這些過程信息。改別人的代碼實在是太蛋疼，想了想，不如自己重新寫一個。
正文
說回正題，先簡單說明一下算法思路（標準數(shù)獨）：
1、先尋找并填寫那些唯一數(shù)單元格。在部分數(shù)獨中有些單元格會因為同行、列、宮內(nèi)題目已知數(shù)的限制，實際只有一個數(shù)可以填，這種單元格就應(yīng)該趁早填好，因為沒有嘗試的必要，不提前處理掉還會影響之后求解的效率。在填寫數(shù)字后，同行、列、宮的候選數(shù)就會減少，可能會出現(xiàn)新的唯一數(shù)單元格，那么繼續(xù)填寫，直到?jīng)]有唯一數(shù)單元格為止。
2、檢查是否已經(jīng)完成游戲，也就是所有單元格都有數(shù)字。部分簡單數(shù)獨一直填唯一數(shù)單元格就可以完成游戲。
3、按照單元格從左到右、從上到下，數(shù)字從小到大的順序嘗試填寫有多個候選數(shù)的單元格，直到全部填完或者發(fā)現(xiàn)有單元格候選數(shù)為空。如果出現(xiàn)無候選數(shù)的單元格說明之前填錯數(shù)導(dǎo)致出現(xiàn)死路，就需要悔步清除上一個單元格填過的數(shù)，換成下一個候選數(shù)繼續(xù)嘗試。如果清除后發(fā)現(xiàn)沒有更大的候選數(shù)可填，說明更早之前就已經(jīng)填錯了，要繼續(xù)悔步并換下一個候選數(shù)。有可能需要連續(xù)悔多步，一直悔步直到有更大的候選數(shù)可填的單元格。如果一路到最開始的單元格都沒法填，說明這個數(shù)獨有問題，無解。
代碼（包括數(shù)獨求解器，求解過程信息，答案存儲三個主要類）：
數(shù)獨求解器
public class SudokuSolver
{
/// <summary>
/// 題目面板
/// </summary>
public SudokuBlock[][] SudokuBoard { get; }
public SudokuSolver(byte[][] board)
{
SudokuBoard = new SudokuBlock[board.Length][];
//初始化數(shù)獨的行
for (int i = 0; i < board.Length; i++)
{
SudokuBoard[i] = new SudokuBlock[board[i].Length];
//初始化每行的列
for (int j = 0; j < board[i].Length; j++)
{
SudokuBoard[i][j] = new SudokuBlock(
board[i][j] > 0
, board[i][j] <= 0 ? new BitArray(board.Length) : null
, board[i][j] > 0 ? (byte?)board[i][j] : null
, (byte)i
, (byte)j);
}
}
}
/// <summary>
/// 求解數(shù)獨
/// </summary>
/// <returns>獲得的解</returns>
public IEnumerable<(SudokuState sudoku, PathTree path)> Solve(bool multiAnswer = false)
{
//初始化各個單元格能填入的數(shù)字
InitCandidate();
var pathRoot0 = new PathTree(null, -1, -1, -1); //填寫路徑樹，在非遞歸方法中用于記錄回退路徑和其他有用信息，初始生成一個根
var path0 = pathRoot0;
//循環(huán)填入能填入的數(shù)字只有一個的單元格，每次填入都可能產(chǎn)生新的唯一數(shù)單元格，直到?jīng)]有唯一數(shù)單元格可填
while (true)
{
if (!FillUniqueNumber(ref path0))
{
break;
}
}
//檢查是否在填唯一數(shù)單元格時就已經(jīng)把所有單元格填滿了
var finish = true;
foreach (var row in SudokuBoard)
{
foreach (var cell in row)
{
if (!cell.IsCondition && !cell.IsUnique)
{
finish = false;
break;
}
}
if (!finish)
{
break;
}
}
if (finish)
{
yield return (new SudokuState(this), path0);
yield break;
}
var pathRoot = new PathTree(null, -1, -1, -1); //填寫路徑樹，在非遞歸方法中用于記錄回退路徑和其他有用信息，初始生成一個根
var path = pathRoot;
var toRe = new List<(SudokuState sudoku, PathTree path)>();
//還存在需要試數(shù)才能求解的單元格，開始暴力搜索
int i = 0, j = 0;
while (true)
{
(i, j) = NextBlock(i, j);
//正常情況下返回-1表示已經(jīng)全部填完
if (i == -1 && j == -1 && !multiAnswer)
{
var pathLast = path;//記住最后一步
var path1 = path;
while(path1.Parent.X != -1 && path1.Parent.Y != -1)
{
path1 = path1.Parent;
}
//將暴力搜索的第一步追加到唯一數(shù)單元格的填寫步驟的最后一步之后，連接成完整的填數(shù)步驟
path0.Children.Add(path1);
path1.Parent = path0;
yield return (new SudokuState(this), pathLast);
break;
}
var numNode = path.Children.LastOrDefault();
//確定要從哪個數(shù)開始進行填入嘗試
var num = numNode == null
? 0
: numNode.Number;
bool filled = false; //是否發(fā)現(xiàn)可以填入的數(shù)
//循環(huán)查看從num開始接下來的候選數(shù)是否能填（num是最后一次填入的數(shù)，傳到Candidate[]的索引器中剛好指向 num + 1是否能填的存儲位，對于標準數(shù)獨，候選數(shù)為 1~9，Candidate的索引范圍就是 0~8）
for (; !SudokuBoard[i][j].IsCondition && !SudokuBoard[i][j].IsUnique && num < SudokuBoard[i][j].Candidate.Length; num++)
{
//如果有可以填的候選數(shù)，理論上不會遇見沒有可以填的情況，這種死路情況已經(jīng)在UpdateCandidate時檢查了
if (SudokuBoard[i][j].Candidate[num] && !path.Children.Any(x => x.Number - 1 == num && !x.Pass))
{
filled = true; //進來了說明單元格有數(shù)可以填
//記錄步驟
var node = new PathTree(SudokuBoard[i][j], i, j, num + 1, path);
path = node;
//如果更新相關(guān)單元格的候選數(shù)時發(fā)現(xiàn)死路（更新函數(shù)會在發(fā)現(xiàn)死路時自動撤銷更新）
(bool canFill, (byte x, byte y)[] setList) updateResult = UpdateCandidate(i, j, (byte)(num + 1));
if (!updateResult.canFill)
{
//記錄這條路是死路
path.SetPass(false);
}
//僅在確認是活路時設(shè)置填入數(shù)字
if (path.Pass)
{
SudokuBoard[i][j].SetNumber((byte)(num + 1));
path.SetList = updateResult.setList;//記錄相關(guān)單元格可填數(shù)更新記錄，方便在回退時撤銷更新
}
else //出現(xiàn)死路，要進行回退，重試這個單元格的其他可填數(shù)字
{
path.Block.SetNumber(null);
path = path.Parent;
}
//填入一個候選數(shù)后跳出循環(huán)，不再繼續(xù)嘗試填入之后的候選數(shù)
break;
}
}
if (!filled)//如果沒有成功填入數(shù)字，說明上一步填入的單元格就是錯的，會導(dǎo)致后面的單元格怎么填都不對，要回退到上一個單元格重新填
{
path.SetPass(false);
path.Block.SetNumber(null);
foreach (var pos in path.SetList)
{
SudokuBoard[pos.x][pos.y].Candidate.Set(path.Number - 1, true);
}
path = path.Parent;
i = path.X < 0 ? 0 : path.X;
j = path.Y < 0 ? 0 : path.Y;
}
}
}
/// <summary>
/// 初始化候選項
/// </summary>
private void InitCandidate()
{
//初始化每行空缺待填的數(shù)字
var rb = new List<BitArray>();
for (int i = 0; i < SudokuBoard.Length; i++)
{
var r = new BitArray(SudokuBoard.Length);
r.SetAll(true);
for (int j = 0; j < SudokuBoard[i].Length; j++)
{
//如果i行j列是條件（題目）給出的數(shù)，設(shè)置數(shù)字不能再填（r[x] == false 表示 i 行不能再填 x + 1，下標加1表示數(shù)獨可用的數(shù)字，下標對應(yīng)的值表示下標加1所表示的數(shù)是否還能填入該行）
if (SudokuBoard[i][j].IsCondition || SudokuBoard[i][j].IsUnique)
{
r.Set(SudokuBoard[i][j].Number.Value - 1, false);
}
}
rb.Add(r);
}
//初始化每列空缺待填的數(shù)字
var cb = new List<BitArray>();
for (int j = 0; j < SudokuBoard[0].Length; j++)
{
var c = new BitArray(SudokuBoard[0].Length);
c.SetAll(true);
for (int i = 0; i < SudokuBoard.Length; i++)
{
if (SudokuBoard[i][j].IsCondition || SudokuBoard[i][j].IsUnique)
{
c.Set(SudokuBoard[i][j].Number.Value - 1, false);
}
}
cb.Add(c);
}
//初始化每宮空缺待填的數(shù)字（目前只能算標準 n×n 數(shù)獨的宮）
var gb = new List<BitArray>();
//n表示每宮應(yīng)有的行、列數(shù)（標準數(shù)獨行列、數(shù)相同）
var n = (int)Sqrt(SudokuBoard.Length);
for (int g = 0; g < SudokuBoard.Length; g++)
{
var gba = new BitArray(SudokuBoard.Length);
gba.SetAll(true);
for (int i = g / n * n; i < g / n * n + n; i++)
{
for (int j = g % n * n; j < g % n * n + n; j++)
{
if (SudokuBoard[i][j].IsCondition || SudokuBoard[i][j].IsUnique)
{
gba.Set(SudokuBoard[i][j].Number.Value - 1, false);
}
}
}
gb.Add(gba);
}
//初始化每格可填的候選數(shù)字
for (int i = 0; i < SudokuBoard.Length; i++)
{
for (int j = 0; j < SudokuBoard[i].Length; j++)
{
if (!SudokuBoard[i][j].IsCondition)
{
var c = SudokuBoard[i][j].Candidate;
c.SetAll(true);
//當前格能填的數(shù)為其所在行、列、宮同時空缺待填的數(shù)字，按位與運算后只有同時能填的候選數(shù)保持1（可填如當前格），否則變成0
// i / n * n + j / n：根據(jù)行號列號計算宮號，
c = c.And(rb[i]).And(cb[j]).And(gb[i / n * n + j / n]);
SudokuBoard[i][j].SetCandidate(c);
}
}
}
}
/// <summary>
/// 求解開始時尋找并填入單元格唯一可填的數(shù)，減少解空間
/// </summary>
/// <returns>是否填入過數(shù)字，如果為false，表示能立即確定待填數(shù)字的單元格已經(jīng)沒有，要開始暴力搜索了</returns>
private bool FillUniqueNumber(ref PathTree path)
{
var filled = false;
for (int i = 0; i < SudokuBoard.Length; i++)
{
for (int j = 0; j < SudokuBoard[i].Length; j++)
{
if (!SudokuBoard[i][j].IsCondition && !SudokuBoard[i][j].IsUnique)
{
var canFillCount = 0;
var index = -1;
for (int k = 0; k < SudokuBoard[i][j].Candidate.Length; k++)
{
if (SudokuBoard[i][j].Candidate[k])
{
index = k;
canFillCount++;
}
if (canFillCount > 1)
{
break;
}
}
if (canFillCount == 0)
{
throw new Exception("有單元格無法填入任何數(shù)字，數(shù)獨無解");
}
if (canFillCount == 1)
{
var num = (byte)(index + 1);
SudokuBoard[i][j].SetNumber(num);
SudokuBoard[i][j].SetUnique();
filled = true;
var upRes = UpdateCandidate(i, j, num);
if (!upRes.canFill)
{
throw new Exception("有單元格無法填入任何數(shù)字，數(shù)獨無解");
}
path = new PathTree(SudokuBoard[i][j], i, j, num, path);
path.SetList = upRes.setList;
}
}
}
}
return filled;
}
/// <summary>
/// 更新單元格所在行、列、宮的其它單元格能填的數(shù)字候選，如果沒有，會撤銷更新
/// </summary>
/// <param name="row">行號</param>
/// <param name="column">列號</param>
/// <param name="canNotFillNumber">要剔除的候選數(shù)字</param>
/// <returns>更新候選數(shù)后，所有被更新的單元格是否都有可填的候選數(shù)字</returns>
private (bool canFill, (byte x, byte y)[] setList) UpdateCandidate(int row, int column, byte canNotFillNumber)
{
var canFill = true;
var list = new List<SudokuBlock>(); // 記錄修改過的單元格，方便撤回修改
bool CanFillNumber(int i, int j)
{
var re = true;
var _canFill = false;
for (int k = 0; k < SudokuBoard[i][j].Candidate.Length; k++)
{
if (SudokuBoard[i][j].Candidate[k])
{
_canFill = true;
break;
}
}
if (!_canFill)
{
re = false;
}
return re;
}
bool Update(int i, int j)
{
if (!(i == row && j == column) && !SudokuBoard[i][j].IsCondition && !SudokuBoard[i][j].IsUnique && SudokuBoard[i][j].Candidate[canNotFillNumber - 1])
{
SudokuBoard[i][j].Candidate.Set(canNotFillNumber - 1, false);
list.Add(SudokuBoard[i][j]);
return CanFillNumber(i, j);
}
else
{
return true;
}
}
//更新該行其余列
for (int j = 0; j < SudokuBoard[row].Length; j++)
{
canFill = Update(row, j);
if (!canFill)
{
break;
}
}
if (canFill) //只在行更新時沒發(fā)現(xiàn)無數(shù)可填的單元格時進行列更新才有意義
{
//更新該列其余行
for (int i = 0; i < SudokuBoard.Length; i++)
{
canFill = Update(i, column);
if (!canFill)
{
break;
}
}
}
if (canFill)//只在行、列更新時都沒發(fā)現(xiàn)無數(shù)可填的單元格時進行宮更新才有意義
{
//更新該宮其余格
//n表示每宮應(yīng)有的行、列數(shù)（標準數(shù)獨行列、數(shù)相同）
var n = (int)Sqrt(SudokuBoard.Length);
//g為宮的編號，根據(jù)行號列號計算
var g = row / n * n + column / n;
for (int i = g / n * n; i < g / n * n + n; i++)
{
for (int j = g % n * n; j < g % n * n + n; j++)
{
canFill = Update(i, j);
if (!canFill)
{
goto canNotFill;
}
}
}
canNotFill:;
}
//如果發(fā)現(xiàn)存在沒有任何數(shù)字可填的單元格，撤回所有候選修改
if (!canFill)
{
foreach (var cell in list)
{
cell.Candidate.Set(canNotFillNumber - 1, true);
}
}
return (canFill, list.Select(x => (x.X, x.Y)).ToArray());
}
/// <summary>
/// 尋找下一個要嘗試填數(shù)的格
/// </summary>
/// <param name="i">起始行號</param>
/// <param name="j">起始列號</param>
/// <returns>找到的下一個行列號，沒有找到返回-1</returns>
private (int x, int y) NextBlock(int i = 0, int j = 0)
{
for (; i < SudokuBoard.Length; i++)
{
for (; j < SudokuBoard[i].Length; j++)
{
if (!SudokuBoard[i][j].IsCondition && !SudokuBoard[i][j].IsUnique && !SudokuBoard[i][j].Number.HasValue)
{
return (i, j);
}
}
j = 0;
}
return (-1, -1);
}
public override string ToString()
{
static string Str(SudokuBlock b)
{
var n1 = new[] { "①", "②", "③", "④", "⑤", "⑥", "⑦", "⑧", "⑨" };
var n2 = new[] { "⑴", "⑵", "⑶", "⑷", "⑸", "⑹", "⑺", "⑻", "⑼" };
return b.Number.HasValue
? b.IsCondition
? " " + b.Number
: b.IsUnique
? n1[b.Number.Value - 1]
: n2[b.Number.Value - 1]
: "▢";
}
return
$@"{Str(SudokuBoard[0][0])},{Str(SudokuBoard[0][1])},{Str(SudokuBoard[0][2])},{Str(SudokuBoard[0][3])},{Str(SudokuBoard[0][4])},{Str(SudokuBoard[0][5])},{Str(SudokuBoard[0][6])},{Str(SudokuBoard[0][7])},{Str(SudokuBoard[0][8])}
{Str(SudokuBoard[1][0])},{Str(SudokuBoard[1][1])},{Str(SudokuBoard[1][2])},{Str(SudokuBoard[1][3])},{Str(SudokuBoard[1][4])},{Str(SudokuBoard[1][5])},{Str(SudokuBoard[1][6])},{Str(SudokuBoard[1][7])},{Str(SudokuBoard[1][8])}
{Str(SudokuBoard[2][0])},{Str(SudokuBoard[2][1])},{Str(SudokuBoard[2][2])},{Str(SudokuBoard[2][3])},{Str(SudokuBoard[2][4])},{Str(SudokuBoard[2][5])},{Str(SudokuBoard[2][6])},{Str(SudokuBoard[2][7])},{Str(SudokuBoard[2][8])}
{Str(SudokuBoard[3][0])},{Str(SudokuBoard[3][1])},{Str(SudokuBoard[3][2])},{Str(SudokuBoard[3][3])},{Str(SudokuBoard[3][4])},{Str(SudokuBoard[3][5])},{Str(SudokuBoard[3][6])},{Str(SudokuBoard[3][7])},{Str(SudokuBoard[3][8])}
{Str(SudokuBoard[4][0])},{Str(SudokuBoard[4][1])},{Str(SudokuBoard[4][2])},{Str(SudokuBoard[4][3])},{Str(SudokuBoard[4][4])},{Str(SudokuBoard[4][5])},{Str(SudokuBoard[4][6])},{Str(SudokuBoard[4][7])},{Str(SudokuBoard[4][8])}
{Str(SudokuBoard[5][0])},{Str(SudokuBoard[5][1])},{Str(SudokuBoard[5][2])},{Str(SudokuBoard[5][3])},{Str(SudokuBoard[5][4])},{Str(SudokuBoard[5][5])},{Str(SudokuBoard[5][6])},{Str(SudokuBoard[5][7])},{Str(SudokuBoard[5][8])}
{Str(SudokuBoard[6][0])},{Str(SudokuBoard[6][1])},{Str(SudokuBoard[6][2])},{Str(SudokuBoard[6][3])},{Str(SudokuBoard[6][4])},{Str(SudokuBoard[6][5])},{Str(SudokuBoard[6][6])},{Str(SudokuBoard[6][7])},{Str(SudokuBoard[6][8])}
{Str(SudokuBoard[7][0])},{Str(SudokuBoard[7][1])},{Str(SudokuBoard[7][2])},{Str(SudokuBoard[7][3])},{Str(SudokuBoard[7][4])},{Str(SudokuBoard[7][5])},{Str(SudokuBoard[7][6])},{Str(SudokuBoard[7][7])},{Str(SudokuBoard[7][8])}
{Str(SudokuBoard[8][0])},{Str(SudokuBoard[8][1])},{Str(SudokuBoard[8][2])},{Str(SudokuBoard[8][3])},{Str(SudokuBoard[8][4])},{Str(SudokuBoard[8][5])},{Str(SudokuBoard[8][6])},{Str(SudokuBoard[8][7])},{Str(SudokuBoard[8][8])}";
}
}
大多數(shù)都有注釋，配合注釋應(yīng)該不難理解，如有問題歡迎評論區(qū)交流。稍微說一下，重載ToString是為了方便調(diào)試和查看狀態(tài)，其中空心方框表示未填寫數(shù)字的單元格，數(shù)字表示題目給出數(shù)字的單元格，圈數(shù)字表示唯一數(shù)單元格填寫的數(shù)字，括號數(shù)字表示有多個候選數(shù)通過嘗試（暴力搜索）確定的數(shù)字。注意類文件最上面有一個using static System.Math; 導(dǎo)入靜態(tài)類，不然每次調(diào)用數(shù)學(xué)函數(shù)都要 Math. ，很煩。
求解過程信息
public class PathTree
{
public PathTree Parent { get; set; }
public List<PathTree> Children { get; } = new List<PathTree>();
public SudokuBlock Block { get; }
public int X { get; }
public int Y { get; }
public int Number { get; }
public bool Pass { get; private set; } = true;
public (byte x, byte y)[] SetList { get; set; }
public PathTree(SudokuBlock block, int x, int y, int number)
{
Block = block;
X = x;
Y = y;
Number = number;
}
public PathTree(SudokuBlock block, int row, int column, int number, PathTree parent)
: this(block, row, column, number)
{
Parent = parent;
Parent.Children.Add(this);
}
public void SetPass(bool pass)
{
Pass = pass;
}
}
其中記錄了每個步驟在哪個單元格填寫了哪個數(shù)字，上一步是哪一步，之后嘗試過哪些步驟，這一步是否會導(dǎo)致之后的步驟出現(xiàn)死路，填寫數(shù)字后影響到的單元格和候選數(shù)字（用來在悔步的時候恢復(fù)相應(yīng)單元格的候選數(shù)字）。
答案存儲
public class SudokuState
{
public SudokuBlock[][] SudokuBoard { get; }
public SudokuState(SudokuSolver sudoku)
{
SudokuBoard = new SudokuBlock[sudoku.SudokuBoard.Length][];
//初始化數(shù)獨的行
for (int i = 0; i < sudoku.SudokuBoard.Length; i++)
{
SudokuBoard[i] = new SudokuBlock[sudoku.SudokuBoard[i].Length];
//初始化每行的列
for (int j = 0; j < sudoku.SudokuBoard[i].Length; j++)
{
SudokuBoard[i][j] = new SudokuBlock(
sudoku.SudokuBoard[i][j].IsCondition
, null
, sudoku.SudokuBoard[i][j].Number
, (byte)i
, (byte)j);
if (sudoku.SudokuBoard[i][j].IsUnique)
{
SudokuBoard[i][j].SetUnique();
}
}
}
}
public override string ToString()
{
static string Str(SudokuBlock b)
{
var n1 = new[] { "①", "②", "③", "④", "⑤", "⑥", "⑦", "⑧", "⑨" };
var n2 = new[] { "⑴", "⑵", "⑶", "⑷", "⑸", "⑹", "⑺", "⑻", "⑼" };
return b.Number.HasValue
? b.IsCondition
? " " + b.Number
: b.IsUnique
? n1[b.Number.Value - 1]
: n2[b.Number.Value - 1]
: "▢";
}
return
$@"{Str(SudokuBoard[0][0])},{Str(SudokuBoard[0][1])},{Str(SudokuBoard[0][2])},{Str(SudokuBoard[0][3])},{Str(SudokuBoard[0][4])},{Str(SudokuBoard[0][5])},{Str(SudokuBoard[0][6])},{Str(SudokuBoard[0][7])},{Str(SudokuBoard[0][8])}
{Str(SudokuBoard[1][0])},{Str(SudokuBoard[1][1])},{Str(SudokuBoard[1][2])},{Str(SudokuBoard[1][3])},{Str(SudokuBoard[1][4])},{Str(SudokuBoard[1][5])},{Str(SudokuBoard[1][6])},{Str(SudokuBoard[1][7])},{Str(SudokuBoard[1][8])}
{Str(SudokuBoard[2][0])},{Str(SudokuBoard[2][1])},{Str(SudokuBoard[2][2])},{Str(SudokuBoard[2][3])},{Str(SudokuBoard[2][4])},{Str(SudokuBoard[2][5])},{Str(SudokuBoard[2][6])},{Str(SudokuBoard[2][7])},{Str(SudokuBoard[2][8])}
{Str(SudokuBoard[3][0])},{Str(SudokuBoard[3][1])},{Str(SudokuBoard[3][2])},{Str(SudokuBoard[3][3])},{Str(SudokuBoard[3][4])},{Str(SudokuBoard[3][5])},{Str(SudokuBoard[3][6])},{Str(SudokuBoard[3][7])},{Str(SudokuBoard[3][8])}
{Str(SudokuBoard[4][0])},{Str(SudokuBoard[4][1])},{Str(SudokuBoard[4][2])},{Str(SudokuBoard[4][3])},{Str(SudokuBoard[4][4])},{Str(SudokuBoard[4][5])},{Str(SudokuBoard[4][6])},{Str(SudokuBoard[4][7])},{Str(SudokuBoard[4][8])}
{Str(SudokuBoard[5][0])},{Str(SudokuBoard[5][1])},{Str(SudokuBoard[5][2])},{Str(SudokuBoard[5][3])},{Str(SudokuBoard[5][4])},{Str(SudokuBoard[5][5])},{Str(SudokuBoard[5][6])},{Str(SudokuBoard[5][7])},{Str(SudokuBoard[5][8])}
{Str(SudokuBoard[6][0])},{Str(SudokuBoard[6][1])},{Str(SudokuBoard[6][2])},{Str(SudokuBoard[6][3])},{Str(SudokuBoard[6][4])},{Str(SudokuBoard[6][5])},{Str(SudokuBoard[6][6])},{Str(SudokuBoard[6][7])},{Str(SudokuBoard[6][8])}
{Str(SudokuBoard[7][0])},{Str(SudokuBoard[7][1])},{Str(SudokuBoard[7][2])},{Str(SudokuBoard[7][3])},{Str(SudokuBoard[7][4])},{Str(SudokuBoard[7][5])},{Str(SudokuBoard[7][6])},{Str(SudokuBoard[7][7])},{Str(SudokuBoard[7][8])}
{Str(SudokuBoard[8][0])},{Str(SudokuBoard[8][1])},{Str(SudokuBoard[8][2])},{Str(SudokuBoard[8][3])},{Str(SudokuBoard[8][4])},{Str(SudokuBoard[8][5])},{Str(SudokuBoard[8][6])},{Str(SudokuBoard[8][7])},{Str(SudokuBoard[8][8])}";
}
}
沒什么好說的，就是保存答案的，因為有些數(shù)獨的解不唯一，將來有機會擴展求多解時避免相互覆蓋。
還有一個輔助類，單元格定義
public class SudokuBlock
{
/// <summary>
/// 填入的數(shù)字
/// </summary>
public byte? Number { get; private set; }
/// <summary>
/// X坐標
/// </summary>
public byte X { get; }
/// <summary>
/// Y坐標
/// </summary>
public byte Y { get; }
/// <summary>
/// 候選數(shù)字，下標所示狀態(tài)表示數(shù)字“下標加1”是否能填入
/// </summary>
public BitArray Candidate { get; private set; }
/// <summary>
/// 是否為條件（題目）給出數(shù)字的單元格
/// </summary>
public bool IsCondition { get; }
/// <summary>
/// 是否為游戲開始就能確定唯一可填數(shù)字的單元格
/// </summary>
public bool IsUnique { get; private set; }
public SudokuBlock(bool isCondition, BitArray candidate, byte? number, byte x, byte y)
{
IsCondition = isCondition;
Candidate = candidate;
Number = number;
IsUnique = false;
X = x;
Y = y;
}
public void SetNumber(byte? number)
{
Number = number;
}
public void SetCandidate(BitArray candidate)
{
Candidate = candidate;
}
public void SetUnique()
{
IsUnique = true;
}
}
測試代碼
static void Main(string[] args)
{
//模板
//byte[][] game = new byte[][] {
// new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
// new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
// new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
// new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
// new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
// new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
// new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
// new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},
// new byte[]{0, 0, 0, 0, 0, 0, 0, 0, 0},};
//這個簡單，無需嘗試，一直填唯一數(shù)單元格，填完后剩下的單元格又有會變唯一數(shù)單元格
//byte[][] game = new byte[][] {
// new byte[]{0, 5, 0, 7, 0, 6, 0, 1, 0},
// new byte[]{0, 8, 0, 0, 9, 0, 0, 6, 0},
// new byte[]{0, 6, 9, 0, 8, 0, 7, 3, 0},
// new byte[]{0, 1, 0, 0, 4, 0, 0, 0, 6},
// new byte[]{6, 0, 7, 1, 0, 3, 8, 0, 5},
// new byte[]{9, 0, 0, 0, 0, 8, 0, 2, 0},
// new byte[]{0, 2, 4, 0, 1, 0, 6, 5, 0},
// new byte[]{0, 7, 0, 0, 6, 0, 0, 4, 0},
// new byte[]{0, 9, 0, 4, 0, 2, 0, 8, 0},};
//可以填一部分唯一數(shù)單元格，剩下一部分需要嘗試，調(diào)試用
//byte[][] game = new byte[][] {
// new byte[]{7, 0, 0, 5, 0, 0, 0, 0, 2},
// new byte[]{0, 3, 0, 0, 0, 4, 6, 0, 0},
// new byte[]{0, 0, 2, 6, 0, 0, 0, 0, 0},
// new byte[]{2, 0, 0, 0, 7, 0, 0, 0, 5},
// new byte[]{5, 0, 0, 1, 0, 3, 0, 0, 6},
// new byte[]{3, 0, 0, 4, 0, 0, 0, 0, 9},
// new byte[]{0, 0, 0, 0, 0, 1, 5, 0, 0},
// new byte[]{0, 0, 7, 2, 0, 0, 0, 4, 0},
// new byte[]{4, 0, 0, 0, 0, 9, 0, 0, 7},};
//全部要靠嘗試來填
byte[][] game = new byte[][] {
new byte[]{1, 0, 0, 2, 0, 0, 3, 0, 0},
new byte[]{0, 4, 0, 5, 0, 0, 0, 6, 0},
new byte[]{0, 0, 0, 7, 0, 0, 8, 0, 0},
new byte[]{3, 0, 0, 0, 0, 7, 0, 0, 0},
new byte[]{0, 9, 0, 0, 0, 0, 0, 5, 0},
new byte[]{0, 0, 0, 6, 0, 0, 0, 0, 7},
new byte[]{0, 0, 2, 0, 0, 4, 0, 0, 0},
new byte[]{0, 5, 0, 0, 0, 6, 0, 9, 0},
new byte[]{0, 0, 8, 0, 0, 1, 0, 0, 3},};
var su = new SudokuSolver(game);
var r = su.Solve();
var r1 = r.First();
static IEnumerable<PathTree> GetPath(PathTree pathTree)
{
List<PathTree> list = new List<PathTree>();
var path = pathTree;
while (path.Parent != null)
{
list.Add(path);
path = path.Parent;
}
return list.Reverse<PathTree>();
}
var p = GetPath(r1.path).Select(x => $"在 {x.X + 1} 行 {x.Y + 1} 列填入 {x.Number}");
foreach(var step in p)
{
Console.WriteLine(step);
}
Console.WriteLine(r1.sudoku);
Console.ReadKey();
}
結(jié)果預(yù)覽：
上面還有，更多步驟，太長，就不全部截下來了。關(guān)于第二張圖詳情請看后面的總結(jié)部分。
總結(jié)
這個數(shù)獨求解器運用了大量 C# 7 的新特性，特別是 本地函數(shù) 和 基于 Tulpe 的簡寫的多返回值函數(shù)，能把本來一團亂的代碼理清楚，寫清爽。 C# 果然是比 Java 這個躺在功勞簿上吃老本不求上進的坑爹語言爽多了。yield return 返回迭代器這種簡直是神仙設(shè)計，隨時想返回就返回，下次進來還能接著上次的地方繼續(xù)跑，寫這種代碼簡直爽翻。另外目前多解求解功能還不可用，只是預(yù)留了集合返回類型和相關(guān)參數(shù)，以后看情況吧。
如果你看過我的這篇文章.Net Core 3 騷操作 之 用 Windows 桌面應(yīng)用開發(fā) Asp.Net Core 網(wǎng)站，你也可以在發(fā)布啟動網(wǎng)站后訪問https://localhost/Sudoku來運行數(shù)獨求解器，注意，調(diào)試狀態(tài)下端口為5001。
本文地址：https://www.cnblogs.com/coredx/p/12173702.html
完整源代碼：Github
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
通過LinQ查詢字符出現(xiàn)次數(shù)的實例方法
這篇文章主要介紹了通過LinQ查詢字符出現(xiàn)次數(shù)的實例方法，大家參考使用吧2013-11-11
這篇文章介紹了WPF實現(xiàn)動畫效果的方法，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-01-01
這篇文章主要為大家詳細介紹了unity使用鏈表實現(xiàn)貪吃蛇游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
WPF調(diào)用WindowsAPI實現(xiàn)屏幕錄制
這篇文章主要為大家詳細介紹了WPF如何調(diào)用WindowsAPI實現(xiàn)屏幕錄制，文中的示例代碼講解詳細，對我們學(xué)習(xí)或工作有一定幫助，感興趣的小伙伴可以了解一下2023-05-05
這篇文章介紹了C#操作結(jié)束進程及子進程的方法，文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-06-06
該方法適應(yīng)應(yīng)用桌面快捷鍵壓縮的文件，zip,rar格式的文件進行解壓！2013-05-05
C#與C++動態(tài)鏈接庫DLL參數(shù)互傳方式
這篇文章主要介紹了C#與C++動態(tài)鏈接庫DLL參數(shù)互傳方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
C# SqlSugar批量執(zhí)行SQL語句及批量更新實體對象的操作方法
SqlSugar 是一款 老牌 .NET開源ORM框架,由果糖大數(shù)據(jù)科技團隊維護和更新 ,開箱即用最易上手的ORM,這篇文章主要介紹了C# SqlSugar批量執(zhí)行SQL語句以及批量更新實體對象,需要的朋友可以參考下2024-07-07
這篇文章主要介紹了C#開發(fā)之微信小程序發(fā)送模板消息功能,需要的朋友可以參考下2017-09-09
本文主要介紹了C#中struct與class的區(qū)別詳解，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-06-06