C# 数独求解算法的实现
作者：coredx 发布时间：2022-04-04 18:48:57
标签：C#,数独
前言
数独是一种有趣的智力游戏，但是部分高难度数独在求解过程中经常出现大量单元格有多个候选数字可以填入，不得不尝试填写某个数字然后继续推导的方法。不幸的是这种方法经常出现填到一半才发现有单元格无数可填，说明之前就有单元格填错了把后面的路堵死了。这时就需要悔步，之前的单元格换个数重新试。然而更坑的是究竟要悔多少步呢？不知道。要换数字的时候该换哪个呢？也不知道。手算时就需要大量草稿纸记录填写情况，不然容易忘了哪些试过哪些没试过。
在朋友那里玩他手机上的数独的时候就发现这个问题很烦，到这里其实就不是一个智力游戏，而是体力游戏了。这种体力活实际上交给电脑才是王道。网上搜了一圈，大多都是Java、vb、C++之类的实现，且多是递归算法。递归有一个问题，随着问题规模的扩大，很容易不小心就把栈撑爆，而且大多数实现只是求出答案就完了，很多求解中的信息就没了，而我更想看看这些过程信息。改别人的代码实在是太蛋疼，想了想，不如自己重新写一个。
正文
说回正题，先简单说明一下算法思路（标准数独）：
1、先寻找并填写那些唯一数单元格。在部分数独中有些单元格会因为同行、列、宫内题目已知数的限制，实际只有一个数可以填，这种单元格就应该趁早填好，因为没有尝试的必要，不提前处理掉还会影响之后求解的效率。在填写数字后，同行、列、宫的候选数就会减少，可能会出现新的唯一数单元格，那么继续填写，直到没有唯一数单元格为止。
2、检查是否已经完成游戏，也就是所有单元格都有数字。部分简单数独一直填唯一数单元格就可以完成游戏。
3、按照单元格从左到右、从上到下，数字从小到大的顺序尝试填写有多个候选数的单元格，直到全部填完或者发现有单元格候选数为空。如果出现无候选数的单元格说明之前填错数导致出现死路，就需要悔步清除上一个单元格填过的数，换成下一个候选数继续尝试。如果清除后发现没有更大的候选数可填，说明更早之前就已经填错了，要继续悔步并换下一个候选数。有可能需要连续悔多步，一直悔步直到有更大的候选数可填的单元格。如果一路到最开始的单元格都没法填，说明这个数独有问题，无解。
代码（包括数独求解器，求解过程信息，答案存储三个主要类）：
数独求解器
public class SudokuSolver
{
/// <summary>
/// 题目面板
/// </summary>
public SudokuBlock[][] SudokuBoard { get; }
public SudokuSolver(byte[][] board)
{
SudokuBoard = new SudokuBlock[board.Length][];
//初始化数独的行
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>
/// 求解数独
/// </summary>
/// <returns>获得的解</returns>
public IEnumerable<(SudokuState sudoku, PathTree path)> Solve(bool multiAnswer = false)
{
//初始化各个单元格能填入的数字
InitCandidate();
var pathRoot0 = new PathTree(null, -1, -1, -1); //填写路径树，在非递归方法中用于记录回退路径和其他有用信息，初始生成一个根
var path0 = pathRoot0;
//循环填入能填入的数字只有一个的单元格，每次填入都可能产生新的唯一数单元格，直到没有唯一数单元格可填
while (true)
{
if (!FillUniqueNumber(ref path0))
{
break;
}
}
//检查是否在填唯一数单元格时就已经把所有单元格填满了
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)>();
//还存在需要试数才能求解的单元格，开始暴力搜索
int i = 0, j = 0;
while (true)
{
(i, j) = NextBlock(i, j);
//正常情况下返回-1表示已经全部填完
if (i == -1 && j == -1 && !multiAnswer)
{
var pathLast = path;//记住最后一步
var path1 = path;
while(path1.Parent.X != -1 && path1.Parent.Y != -1)
{
path1 = path1.Parent;
}
//将暴力搜索的第一步追加到唯一数单元格的填写步骤的最后一步之后，连接成完整的填数步骤
path0.Children.Add(path1);
path1.Parent = path0;
yield return (new SudokuState(this), pathLast);
break;
}
var numNode = path.Children.LastOrDefault();
//确定要从哪个数开始进行填入尝试
var num = numNode == null
? 0
: numNode.Number;
bool filled = false; //是否发现可以填入的数
//循环查看从num开始接下来的候选数是否能填（num是最后一次填入的数，传到Candidate[]的索引器中刚好指向 num + 1是否能填的存储位，对于标准数独，候选数为 1~9，Candidate的索引范围就是 0~8）
for (; !SudokuBoard[i][j].IsCondition && !SudokuBoard[i][j].IsUnique && num < SudokuBoard[i][j].Candidate.Length; num++)
{
//如果有可以填的候选数，理论上不会遇见没有可以填的情况，这种死路情况已经在UpdateCandidate时检查了
if (SudokuBoard[i][j].Candidate[num] && !path.Children.Any(x => x.Number - 1 == num && !x.Pass))
{
filled = true; //进来了说明单元格有数可以填
//记录步骤
var node = new PathTree(SudokuBoard[i][j], i, j, num + 1, path);
path = node;
//如果更新相关单元格的候选数时发现死路（更新函数会在发现死路时自动撤销更新）
(bool canFill, (byte x, byte y)[] setList) updateResult = UpdateCandidate(i, j, (byte)(num + 1));
if (!updateResult.canFill)
{
//记录这条路是死路
path.SetPass(false);
}
//仅在确认是活路时设置填入数字
if (path.Pass)
{
SudokuBoard[i][j].SetNumber((byte)(num + 1));
path.SetList = updateResult.setList;//记录相关单元格可填数更新记录，方便在回退时撤销更新
}
else //出现死路，要进行回退，重试这个单元格的其他可填数字
{
path.Block.SetNumber(null);
path = path.Parent;
}
//填入一个候选数后跳出循环，不再继续尝试填入之后的候选数
break;
}
}
if (!filled)//如果没有成功填入数字，说明上一步填入的单元格就是错的，会导致后面的单元格怎么填都不对，要回退到上一个单元格重新填
{
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()
{
//初始化每行空缺待填的数字
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列是条件（题目）给出的数，设置数字不能再填（r[x] == false 表示 i 行不能再填 x + 1，下标加1表示数独可用的数字，下标对应的值表示下标加1所表示的数是否还能填入该行）
if (SudokuBoard[i][j].IsCondition || SudokuBoard[i][j].IsUnique)
{
r.Set(SudokuBoard[i][j].Number.Value - 1, false);
}
}
rb.Add(r);
}
//初始化每列空缺待填的数字
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);
}
//初始化每宫空缺待填的数字（目前只能算标准 n×n 数独的宫）
var gb = new List<BitArray>();
//n表示每宫应有的行、列数（标准数独行列、数相同）
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);
}
//初始化每格可填的候选数字
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);
//当前格能填的数为其所在行、列、宫同时空缺待填的数字，按位与运算后只有同时能填的候选数保持1（可填如当前格），否则变成0
// i / n * n + j / n：根据行号列号计算宫号，
c = c.And(rb[i]).And(cb[j]).And(gb[i / n * n + j / n]);
SudokuBoard[i][j].SetCandidate(c);
}
}
}
}
/// <summary>
/// 求解开始时寻找并填入单元格唯一可填的数，减少解空间
/// </summary>
/// <returns>是否填入过数字，如果为false，表示能立即确定待填数字的单元格已经没有，要开始暴力搜索了</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("有单元格无法填入任何数字，数独无解");
}
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("有单元格无法填入任何数字，数独无解");
}
path = new PathTree(SudokuBoard[i][j], i, j, num, path);
path.SetList = upRes.setList;
}
}
}
}
return filled;
}
/// <summary>
/// 更新单元格所在行、列、宫的其它单元格能填的数字候选，如果没有，会撤销更新
/// </summary>
/// <param name="row">行号</param>
/// <param name="column">列号</param>
/// <param name="canNotFillNumber">要剔除的候选数字</param>
/// <returns>更新候选数后，所有被更新的单元格是否都有可填的候选数字</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) //只在行更新时没发现无数可填的单元格时进行列更新才有意义
{
//更新该列其余行
for (int i = 0; i < SudokuBoard.Length; i++)
{
canFill = Update(i, column);
if (!canFill)
{
break;
}
}
}
if (canFill)//只在行、列更新时都没发现无数可填的单元格时进行宫更新才有意义
{
//更新该宫其余格
//n表示每宫应有的行、列数（标准数独行列、数相同）
var n = (int)Sqrt(SudokuBoard.Length);
//g为宫的编号，根据行号列号计算
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:;
}
//如果发现存在没有任何数字可填的单元格，撤回所有候选修改
if (!canFill)
{
foreach (var cell in list)
{
cell.Candidate.Set(canNotFillNumber - 1, true);
}
}
return (canFill, list.Select(x => (x.X, x.Y)).ToArray());
}
/// <summary>
/// 寻找下一个要尝试填数的格
/// </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])}";
}
}
大多数都有注释，配合注释应该不难理解，如有问题欢迎评论区交流。稍微说一下，重载ToString是为了方便调试和查看状态，其中空心方框表示未填写数字的单元格，数字表示题目给出数字的单元格，圈数字表示唯一数单元格填写的数字，括号数字表示有多个候选数通过尝试（暴力搜索）确定的数字。注意类文件最上面有一个using static System.Math; 导入静态类，不然每次调用数学函数都要 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;
}
}
其中记录了每个步骤在哪个单元格填写了哪个数字，上一步是哪一步，之后尝试过哪些步骤，这一步是否会导致之后的步骤出现死路，填写数字后影响到的单元格和候选数字（用来在悔步的时候恢复相应单元格的候选数字）。
答案存储
public class SudokuState
{
public SudokuBlock[][] SudokuBoard { get; }
public SudokuState(SudokuSolver sudoku)
{
SudokuBoard = new SudokuBlock[sudoku.SudokuBoard.Length][];
//初始化数独的行
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])}";
}
}
没什么好说的，就是保存答案的，因为有些数独的解不唯一，将来有机会扩展求多解时避免相互覆盖。
还有一个辅助类，单元格定义
public class SudokuBlock
{
/// <summary>
/// 填入的数字
/// </summary>
public byte? Number { get; private set; }
/// <summary>
/// X坐标
/// </summary>
public byte X { get; }
/// <summary>
/// Y坐标
/// </summary>
public byte Y { get; }
/// <summary>
/// 候选数字，下标所示状态表示数字“下标加1”是否能填入
/// </summary>
public BitArray Candidate { get; private set; }
/// <summary>
/// 是否为条件（题目）给出数字的单元格
/// </summary>
public bool IsCondition { get; }
/// <summary>
/// 是否为游戏开始就能确定唯一可填数字的单元格
/// </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},};
//这个简单，无需尝试，一直填唯一数单元格，填完后剩下的单元格又有会变唯一数单元格
//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},};
//可以填一部分唯一数单元格，剩下一部分需要尝试，调试用
//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();
}
结果预览：
上面还有，更多步骤，太长，就不全部截下来了。关于第二张图详情请看后面的总结部分。
总结
这个数独求解器运用了大量 C# 7 的新特性，特别是 本地函数 和 基于 Tulpe 的简写的多返回值函数，能把本来一团乱的代码理清楚，写清爽。 C# 果然是比 Java 这个躺在功劳簿上吃老本不求上进的坑爹语言爽多了。yield return 返回迭代器这种简直是神仙设计，随时想返回就返回，下次进来还能接着上次的地方继续跑，写这种代码简直爽翻。另外目前多解求解功能还不可用，只是预留了集合返回类型和相关参数，以后看情况吧。
如果你看过我的这篇文章.Net Core 3 骚操作 之 用 Windows 桌面应用开发 Asp.Net Core 网站，你也可以在发布启动网站后访问https://localhost/Sudoku来运行数独求解器，注意，调试状态下端口为5001。
本文地址：https://www.cnblogs.com/coredx/p/12173702.html
完整源代码：Github
来源：https://www.cnblogs.com/coredx/p/12173702.html
0
投稿猜你喜欢
前言在阅读本文之前, 希望你可以思考一下下面几个问题, 带着问题去阅读文章会获得更好的效果。发送消息的时候, 当Broker挂掉了,消息体还- 具体详细介绍请看下文：在使用文件进行交互数据的应用来说，使用FTP服务器是一个很好的选择。本文使用Apache Jakarta Common
- 什么是NIO？线程在处理数据时，如果线程还处于将数据从channel读到buffer的这段时间内，线程可以去做别的事情，等数据都读到buff
- Flyway是一款开源的数据库版本管理工具，它更倾向于规约优于配置的方式。第一步:pom.xml添加maven依赖<!-- https
- springboot + docker + jenkins自动化部署项目，jenkins、mysql、redis都是docker运行的，并且
- 1. SpringBoot ResponseBody 返回值中null值处理@PostMapping(path = "/test&
- 安装java的运行环境IDEA一 找到并下载IDEA百度IDEA找到官网，往下翻找到Java并点击找到 并下载IDEA右边为开源的免费版本，
- 问题描述平常用的是java8,最近在学习java的新特性。这就需要从java8往更高的java版本切换。由于还在使用java8,测试完新特性
- 添加记录后获取主键ID，这是一个很常见的需求，特别是在一次前端调用中需要插入多个表的场景。除了添加单条记录时获取主键值，有时候可能需要获取批
- 最近在使用 url 的 queryString 传递参数时，因为参数的值，被DES加密了，而加密得到的是 Base64的编码字符串类似于：z
- 因为公司现在换成了nacos，所以自己写了demo学习一下。结果第一步就走不下去。在使用nacos-config读取nacos配置时。发现b
- 更新: 工作中突然想起来，关于Yaml的使用，并不属于Spring的范畴，是org.yaml.snakeyaml处理的。所以yaml的使用应
- 题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。经典题，不多说，直接上代码import java.
- 一、@RestController 注解在 Spring Boot 中的 Controller 中使用 @RestController 注解
- Spring Cloud Gateway使用Spring Cloud Gateway是一个基于Spring Boot 2.x和Spring&
- SpringBoot的持久化层可以是Spring内置的轻量级JdbcTemplate、也可以是Hibernate或Mybatis等等，只需要
- List 是在开发中比较常用的集合，今天总结一下 Java 中初始化 List 的几种方式。1、常规方式List<String>
- 1、配置maven环境变量，将maven安装的bin⽬录添加到path路径中（此电脑->属性->高级系统设置->环境变量-
- 本人是从事互联网金融行业的，所以会接触到一些金融类的问题，常见的一种就是数字转汉字大小写的问题。所以抽空就写了一个小小的工具类，实现了数字转
- 原因分析使用ajax从前台页面传输数据到后台controller控制器的时候，出现中文乱码其实乱码问题出现的原因，就是由于默认的tomcat
