C#中怎么實現(xiàn)一個數(shù)獨求解算法

C#中怎么實現(xiàn)一個數(shù)獨求解算法，針對這個問題，這篇文章詳細介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

10年積累的網(wǎng)站制作、成都做網(wǎng)站經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認識你，你也不認識我。但先建設(shè)網(wǎng)站后付款的網(wǎng)站建設(shè)流程，更有平壩免費網(wǎng)站建設(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 path2 = path; while(path2.Parent.X != -1 && path2.Parent.Y != -1) { path2 = path2.Parent; } //將暴力搜索的第一步追加到唯一數(shù)單元格的填寫步驟的最后一步之后，連接成完整的填數(shù)步驟 path0.Children.Add(path2); path2.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(); }

關(guān)于C#中怎么實現(xiàn)一個數(shù)獨求解算法問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識。

當前文章：C#中怎么實現(xiàn)一個數(shù)獨求解算法
分享路徑：http://bm7419.com/article14/igoede.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、App設(shè)計、企業(yè)建站、虛擬主機、自適應(yīng)網(wǎng)站、定制網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容