数独是一种有趣的智力游戏，但是部分高难度数独在求解过程中经常出现大量单元格有多个候选数字可以填入，不得不尝试填写某个数字然后继续推导的方法。不幸的是这种方法经常出现填到一半才发现有单元格无数可填，说明之前就有单元格填错了把后面的路堵死了。这时就需要悔步，之前的单元格换个数重新试。然而更坑的是究竟要悔多少步呢？不知道。要换数字的时候该换哪个呢？也不知道。手算时就需要大量草稿纸记录填写情况，不然容易忘了哪些试过哪些没试过。 在朋友那里玩他手机上的数独的时候就发现这个问题很烦，到这里其实就不是一个智力游戏，而是体力游戏了。这种体力活实际上交给电脑才是王道。网上搜了一圈，大多都是Java、vb、C++之类的实现，且多是递归算法。递归有一个问题，随着问题规模的扩大，很容易不小心就把栈撑爆，而且大多数实现只是求出答案就完了，很多求解中的信息就没了，而我更想看看这些过程信息。改别人的代码实在是太蛋疼，想了想，不如自己重新写一个。 正文 说回正题，先简单说明一下算法思路（标准数独）： 1、先寻找并填写那些唯一数单元格。在部分数独中有些单元格会因为同行、列、宫内题目已知数的限制，实际只有一个数可以填，这种单元格就应该趁早填好，因为没有尝试的必要，不提前处理掉还会影响之后求解的效率。在填写数字后，同行、列、宫的候选数就会减少，可能会出现新的唯一数单元格，那么继续填写，直到没有唯一数单元格为止。 2、检查是否已经完成游戏，也就是所有单元格都有数字。部分简单数独一直填唯一数单元格就可以完成游戏。 3、按照单元格从左到右、从上到下，数字从小到大的顺序尝试填写有多个候选数的单元格，直到全部填完或者发现有单元格候选数为空。如果出现无候选数的单元格说明之前填错数导致出现死路，就需要悔步清除上一个单元格填过的数，换成下一个候选数继续尝试。如果清除后发现没有更大的候选数可填，说明更早之前就已经填错了，要继续悔步并换下一个候选数。有可能需要连续悔多步，一直悔步直到有更大的候选数可填的单元格。如果一路到最开始的单元格都没法填，说明这个数独有问题，无解。 代码（包括数独求解器，求解过程信息，答案存储三个主要类）： 数独求解器 View Code 大多数都有注释，配合注释应该不难理解，如有问题欢迎评论区交流。稍微说一下，重载ToString是为了方便调试和查看状态，其中空心方框表示未填写数字的单元格，数字表示题目给出数字的单元格，圈数字表示唯一数单元格填写的数字，括号数字表示有多个候选数通过尝试（暴力搜索）确定的数字。注意类文件最上面有一个 using static System.Math; 导入静态类，不然每次调用数学函数都要 Math. ，很烦。 求解过程信息 View Code 其中记录了每个步骤在哪个单元格填写了哪个数字，上一步是哪一步，之后尝试过哪些步骤，这一步是否会导致之后的步骤出现死路，填写数字后影响到的单元格和候选数字（用来在悔步的时候恢复相应单元格的候选数字）。 答案存储 View Code 没什么好说的，就是保存答案的，因为有些数独的解不唯一，将来有机会扩展求多解时避免相互覆盖。 还有一个辅助类，单元格定义 View Code 测试代码 View Code 结果预览： 上面还有，更多步骤，太长，就不全部截下来了。关于第二张图详情请看后面的总结部分。 总结 这个数独求解器运用了大量 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 　　里面有各种小东西，这只是其中之一，不嫌弃的话可以Star一下。https://www.cnblogs.com/coredx/p/12173702.html