C# 数独求解算法的实现
前言
数独是一种有趣的智力游戏，但是部分高难度数独在求解过程中经常出现大量单元格有多个候选数字可以填入，不得不尝试填写某个数字然后继续推导的方法。不幸的是这种方法经常出现填到一半才发现有单元格无数可填，说明之前就有单元格填错了把后面的路堵死了。这时就需要悔步，之前的单元格换个数重新试。然而更坑的是究竟要悔多少步呢？不知道。要换数字的时候该换哪个呢？也不知道。手算时就需要大量草稿纸记录填写情况，不然容易忘了哪些试过哪些没试过。
在朋友那里玩他手机上的数独的时候就发现这个问题很烦，到这里其实就不是一个智力游戏，而是体力游戏了。这种体力活实际上交给电脑才是王道。网上搜了一圈，大多都是Java、vb、C++之类的实现，且多是递归算法。递归有一个问题，随着问题规模的扩大，很容易不小心就把栈撑爆，而且大多数实现只是求出答案就完了，很多求解中的信息就没了，而我更想看看这些过程信息。改别人的代码实在是太蛋疼，想了想，不如自己重新写一个。
正文
说回正题，先简单说明一下算法思路（标准数独）：
1、先寻找并填写那些唯一数单元格。在部分数独中有些单元格会因为同行、列、宫内题目已知数的限制，实际只有一个数可以填，这种单元格就应该趁早填好，因为没有尝试的必要，不提前处理掉还会影响之后求解的效率。在填写数字后，同行、列、宫的候选数就会减少，可能会出现新的唯一数单元格，那么继续填写，直到没有唯一数单元格为止。
2、检查是否已经完成游戏，也就是所有单元格都有数字。部分简单数独一直填唯一数单元格就可以完成游戏。
3、按照单元格从左到右、从上到下，数字从小到大的顺序尝试填写有多个候选数的单元格，直到全部填完或者发现有单元格候选数为空。如果出现无候选数的单元格说明之前填错数导致出现死路，就需要悔步清除上一个单元格填过的数，换成下一个候选数继续尝试。如果清除后发现没有更大的候选数可填，说明更早之前就已经填错了，要继续悔步并换下一个候选数。有可能需要连续悔多步，一直悔步直到有更大的候选数可填的单元格。如果一路到最开始的单元格都没法填，说明这个数独有问题，无解。
代码（包括数独求解器，求解过程信息，答案存储三个主要类）：
数独求解器
publicclassSudokuSolver
{
///
///题目面板
///
publicSudokuBlock[][]SudokuBoard{get;}
publicSudokuSolver(byte[][]board)
{
SudokuBoard=newSudokuBlock[board.Length][];
//初始化数独的行
for(inti=0;i0
,board[i][j]<=0?newBitArray(board.Length):null
,board[i][j]>0?(byte?)board[i][j]:null
,(byte)i
,(byte)j);
}
}
}
///
///求解数独
///
///获得的解
publicIEnumerable<(SudokuStatesudoku,PathTreepath)>Solve(boolmultiAnswer=false)
{
//初始化各个单元格能填入的数字
InitCandidate();
varpathRoot0=newPathTree(null,-1,-1,-1);//填写路径树，在非递归方法中用于记录回退路径和其他有用信息，初始生成一个根
varpath0=pathRoot0;
//循环填入能填入的数字只有一个的单元格，每次填入都可能产生新的唯一数单元格，直到没有唯一数单元格可填
while(true)
{
if(!FillUniqueNumber(refpath0))
{
break;
}
}
//检查是否在填唯一数单元格时就已经把所有单元格填满了
varfinish=true;
foreach(varrowinSudokuBoard)
{
foreach(varcellinrow)
{
if(!cell.IsCondition&&!cell.IsUnique)
{
finish=false;
break;
}
}
if(!finish)
{
break;
}
}
if(finish)
{
yieldreturn(newSudokuState(this),path0);
yieldbreak;
}
varpathRoot=newPathTree(null,-1,-1,-1);//填写路径树，在非递归方法中用于记录回退路径和其他有用信息，初始生成一个根
varpath=pathRoot;
vartoRe=newList<(SudokuStatesudoku,PathTreepath)>();
//还存在需要试数才能求解的单元格，开始暴力搜索
inti=0,j=0;
while(true)
{
(i,j)=NextBlock(i,j);
//正常情况下返回-1表示已经全部填完
if(i==-1&&j==-1&&!multiAnswer)
{
varpathLast=path;//记住最后一步
varpath1=path;
while(path1.Parent.X!=-1&&path1.Parent.Y!=-1)
{
path1=path1.Parent;
}
//将暴力搜索的第一步追加到唯一数单元格的填写步骤的最后一步之后，连接成完整的填数步骤
path0.Children.Add(path1);
path1.Parent=path0;
yieldreturn(newSudokuState(this),pathLast);
break;
}
varnumNode=path.Children.LastOrDefault();
//确定要从哪个数开始进行填入尝试
varnum=numNode==null
?0
:numNode.Number;
boolfilled=false;//是否发现可以填入的数
//循环查看从num开始接下来的候选数是否能填（num是最后一次填入的数，传到Candidate[]的索引器中刚好指向num+1是否能填的存储位，对于标准数独，候选数为1~9，Candidate的索引范围就是0~8）
for(;!SudokuBoard[i][j].IsCondition&&!SudokuBoard[i][j].IsUnique&&numx.Number-1==num&&!x.Pass))
{
filled=true;//进来了说明单元格有数可以填
//记录步骤
varnode=newPathTree(SudokuBoard[i][j],i,j,num+1,path);
path=node;
//如果更新相关单元格的候选数时发现死路（更新函数会在发现死路时自动撤销更新）
(boolcanFill,(bytex,bytey)[]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(varposinpath.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;
}
}
}
///
///初始化候选项
///
privatevoidInitCandidate()
{
//初始化每行空缺待填的数字
varrb=newList();
for(inti=0;i();
for(intj=0;j();
//n表示每宫应有的行、列数（标准数独行列、数相同）
varn=(int)Sqrt(SudokuBoard.Length);
for(intg=0;g
///求解开始时寻找并填入单元格唯一可填的数，减少解空间
///
///是否填入过数字，如果为false，表示能立即确定待填数字的单元格已经没有，要开始暴力搜索了
privateboolFillUniqueNumber(refPathTreepath)
{
varfilled=false;
for(inti=0;i1)
{
break;
}
}
if(canFillCount==0)
{
thrownewException("有单元格无法填入任何数字，数独无解");
}
if(canFillCount==1)
{
varnum=(byte)(index+1);
SudokuBoard[i][j].SetNumber(num);
SudokuBoard[i][j].SetUnique();
filled=true;
varupRes=UpdateCandidate(i,j,num);
if(!upRes.canFill)
{
thrownewException("有单元格无法填入任何数字，数独无解");
}
path=newPathTree(SudokuBoard[i][j],i,j,num,path);
path.SetList=upRes.setList;
}
}
}
}
returnfilled;
}
///
///更新单元格所在行、列、宫的其它单元格能填的数字候选，如果没有，会撤销更新
///
///行号
///列号
///要剔除的候选数字
///更新候选数后，所有被更新的单元格是否都有可填的候选数字
private(boolcanFill,(bytex,bytey)[]setList)UpdateCandidate(introw,intcolumn,bytecanNotFillNumber)
{
varcanFill=true;
varlist=newList();//记录修改过的单元格，方便撤回修改
boolCanFillNumber(inti,intj)
{
varre=true;
var_canFill=false;
for(intk=0;k(x.X,x.Y)).ToArray());
}
///
///寻找下一个要尝试填数的格
///
///起始行号
///起始列号
///找到的下一个行列号，没有找到返回-1
private(intx,inty)NextBlock(inti=0,intj=0)
{
for(;i
大多数都有注释，配合注释应该不难理解，如有问题欢迎评论区交流。稍微说一下，重载ToString是为了方便调试和查看状态，其中空心方框表示未填写数字的单元格，数字表示题目给出数字的单元格，圈数字表示唯一数单元格填写的数字，括号数字表示有多个候选数通过尝试（暴力搜索）确定的数字。注意类文件最上面有一个usingstaticSystem.Math;导入静态类，不然每次调用数学函数都要Math.，很烦。
求解过程信息
publicclassPathTree
{
publicPathTreeParent{get;set;}
publicListChildren{get;}=newList();
publicSudokuBlockBlock{get;}
publicintX{get;}
publicintY{get;}
publicintNumber{get;}
publicboolPass{get;privateset;}=true;
public(bytex,bytey)[]SetList{get;set;}
publicPathTree(SudokuBlockblock,intx,inty,intnumber)
{
Block=block;
X=x;
Y=y;
Number=number;
}
publicPathTree(SudokuBlockblock,introw,intcolumn,intnumber,PathTreeparent)
:this(block,row,column,number)
{
Parent=parent;
Parent.Children.Add(this);
}
publicvoidSetPass(boolpass)
{
Pass=pass;
}
}
其中记录了每个步骤在哪个单元格填写了哪个数字，上一步是哪一步，之后尝试过哪些步骤，这一步是否会导致之后的步骤出现死路，填写数字后影响到的单元格和候选数字（用来在悔步的时候恢复相应单元格的候选数字）。
答案存储
publicclassSudokuState
{
publicSudokuBlock[][]SudokuBoard{get;}
publicSudokuState(SudokuSolversudoku)
{
SudokuBoard=newSudokuBlock[sudoku.SudokuBoard.Length][];
//初始化数独的行
for(inti=0;i
没什么好说的，就是保存答案的，因为有些数独的解不唯一，将来有机会扩展求多解时避免相互覆盖。
还有一个辅助类，单元格定义
publicclassSudokuBlock
{
///
///填入的数字
///
publicbyte?Number{get;privateset;}
///
///X坐标
///
publicbyteX{get;}
///
///Y坐标
///
publicbyteY{get;}
///
///候选数字，下标所示状态表示数字“下标加1”是否能填入
///
publicBitArrayCandidate{get;privateset;}
///
///是否为条件（题目）给出数字的单元格
///
publicboolIsCondition{get;}
///
///是否为游戏开始就能确定唯一可填数字的单元格
///
publicboolIsUnique{get;privateset;}
publicSudokuBlock(boolisCondition,BitArraycandidate,byte?number,bytex,bytey)
{
IsCondition=isCondition;
Candidate=candidate;
Number=number;
IsUnique=false;
X=x;
Y=y;
}
publicvoidSetNumber(byte?number)
{
Number=number;
}
publicvoidSetCandidate(BitArraycandidate)
{
Candidate=candidate;
}
publicvoidSetUnique()
{
IsUnique=true;
}
}
测试代码
staticvoidMain(string[]args)
{
//模板
//byte[][]game=newbyte[][]{
//newbyte[]{0,0,0,0,0,0,0,0,0},
//newbyte[]{0,0,0,0,0,0,0,0,0},
//newbyte[]{0,0,0,0,0,0,0,0,0},
//newbyte[]{0,0,0,0,0,0,0,0,0},
//newbyte[]{0,0,0,0,0,0,0,0,0},
//newbyte[]{0,0,0,0,0,0,0,0,0},
//newbyte[]{0,0,0,0,0,0,0,0,0},
//newbyte[]{0,0,0,0,0,0,0,0,0},
//newbyte[]{0,0,0,0,0,0,0,0,0},};
//这个简单，无需尝试，一直填唯一数单元格，填完后剩下的单元格又有会变唯一数单元格
//byte[][]game=newbyte[][]{
//newbyte[]{0,5,0,7,0,6,0,1,0},
//newbyte[]{0,8,0,0,9,0,0,6,0},
//newbyte[]{0,6,9,0,8,0,7,3,0},
//newbyte[]{0,1,0,0,4,0,0,0,6},
//newbyte[]{6,0,7,1,0,3,8,0,5},
//newbyte[]{9,0,0,0,0,8,0,2,0},
//newbyte[]{0,2,4,0,1,0,6,5,0},
//newbyte[]{0,7,0,0,6,0,0,4,0},
//newbyte[]{0,9,0,4,0,2,0,8,0},};
//可以填一部分唯一数单元格，剩下一部分需要尝试，调试用
//byte[][]game=newbyte[][]{
//newbyte[]{7,0,0,5,0,0,0,0,2},
//newbyte[]{0,3,0,0,0,4,6,0,0},
//newbyte[]{0,0,2,6,0,0,0,0,0},
//newbyte[]{2,0,0,0,7,0,0,0,5},
//newbyte[]{5,0,0,1,0,3,0,0,6},
//newbyte[]{3,0,0,4,0,0,0,0,9},
//newbyte[]{0,0,0,0,0,1,5,0,0},
//newbyte[]{0,0,7,2,0,0,0,4,0},
//newbyte[]{4,0,0,0,0,9,0,0,7},};
//全部要靠尝试来填
byte[][]game=newbyte[][]{
newbyte[]{1,0,0,2,0,0,3,0,0},
newbyte[]{0,4,0,5,0,0,0,6,0},
newbyte[]{0,0,0,7,0,0,8,0,0},
newbyte[]{3,0,0,0,0,7,0,0,0},
newbyte[]{0,9,0,0,0,0,0,5,0},
newbyte[]{0,0,0,6,0,0,0,0,7},
newbyte[]{0,0,2,0,0,4,0,0,0},
newbyte[]{0,5,0,0,0,6,0,9,0},
newbyte[]{0,0,8,0,0,1,0,0,3},};
varsu=newSudokuSolver(game);
varr=su.Solve();
varr1=r.First();
staticIEnumerableGetPath(PathTreepathTree)
{
Listlist=newList();
varpath=pathTree;
while(path.Parent!=null)
{
list.Add(path);
path=path.Parent;
}
returnlist.Reverse();
}
varp=GetPath(r1.path).Select(x=>$"在{x.X+1}行{x.Y+1}列填入{x.Number}");
foreach(varstepinp)
{
Console.WriteLine(step);
}
Console.WriteLine(r1.sudoku);
Console.ReadKey();
}
结果预览：
上面还有，更多步骤，太长，就不全部截下来了。关于第二张图详情请看后面的总结部分。
总结
这个数独求解器运用了大量C#7的新特性，特别是本地函数和基于Tulpe的简写的多返回值函数，能把本来一团乱的代码理清楚，写清爽。C#果然是比Java这个躺在功劳簿上吃老本不求上进的坑爹语言爽多了。yieldreturn返回迭代器这种简直是神仙设计，随时想返回就返回，下次进来还能接着上次的地方继续跑，写这种代码简直爽翻。另外目前多解求解功能还不可用，只是预留了集合返回类型和相关参数，以后看情况吧。
如果你看过我的这篇文章.NetCore3骚操作之用Windows桌面应用开发Asp.NetCore网站，你也可以在发布启动网站后访问https://localhost/Sudoku来运行数独求解器，注意，调试状态下端口为5001。
本文地址：https://www.cnblogs.com/coredx/p/12173702.html
完整源代码：Github
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。