数独解法学习，好像是递归剪枝了

aoe1981

对数独忽来兴趣是看了大神lsdongjh的帖子和附件：

递归学习之--数独解法
http://club.excelhome.net/thread-1521550-1-1.html
(出处: ExcelHome技术论坛)



便很想知道计算机的数独算法究竟是什么样的？无奈读代码的水平极低，没敢细看，便自己瞎鼓捣，做了一个。


界面如图：







我做的附件是不能够自动出题的，但是可以验证题目的合规性，可以解题，而且希望找到所有解。这些很普通，让我骄傲的反倒是我自己鼓捣的“难度等级”。

难度等级和“提示数”的多寡关联性不大，我是根据“解的个数”、“逻辑断定格”、“递归测试格”的数量划分的，自然也不完全科学，仅供娱乐。

“递归”是个让人恐怖、头疼的算法，有时排错非人脑可以完全想清楚，我手动排错验证了一道题：



这道题的结果寻找的过程是一张树形图：




所以“二叉”，是因为我在代码中总是将“可填数字个数”从少到多排序。看了看这个图，我忽然感觉：这难道是所谓“剪枝”？

如果一道数独谜题中递归格有49格，按理来说递归深度是49层，但是我的算法处理下来只有8层，这是怎么做的呢？

当测试填充一个“递归格”后，会影响一众格子的“可填数字个数”，主要有：

1.同行格子；

2.同列格子；

3.同宫格子；

4.同宫其余两行两列贯通“井”字排除确定的格子。

第4条或许我叙述的有点费劲，但对爱好数独的人来说，这只是小菜一碟，算不得高级。有了对这一众“连带格”的后续处理，便好像实现了“剪枝”，不过，估计也是我的一厢情愿，以前粗粗看过“α、β剪枝”的，好像与之距离尚远。哈哈，只要实现了就行了。

我的附件在做下面一道题时，效率还可以：



当然，也不是特别突出。在有些谜题上（特别是解不唯一的），偶尔运行速度较慢，不敢自夸。

最后，向大神lsdongjh表示敬意，本想在贵帖中跟帖，但为了集中自已的发帖，便于以后查阅，又独自发了新帖。

第一阶段附件如下：
数独解法学习_aoe1981.zip (78.6 KB, 下载次数: 31)

2020-2-23 16:23 上传

点击文件名下载附件

（半天传不了附件，原来是浏览器的原因，edge问题就是多，还是360极速好一些）

（附件更新至9楼，主要是调整难度等级，备份了一些数独难题，详情见8楼、9楼说明）

（再次更新：针对合乎数独规则但无解的情况增加了一句恢复事件响应的代码，见后面11楼左右回帖）
（附件更新至18楼：增加搜索顺序、运行限时选项，以适应更多的谜题）


第二阶段附件如下：

数独解法学习2.0_位运算优化_aoe1981.zip (81.23 KB, 下载次数: 12)

2020-2-27 20:57 上传

点击文件名下载附件

（更新说明在24楼，主要参考20楼大神yangyangzhifeng给出的“采用位运算”的建议，重构了代码，主要涉及核心数组变量结构的简化，调用子过程的减少等，平均提速40%~70%不等）

第三阶段附件如下：

数独解法学习3.0_位运算优化四种基本数独技巧固定递归路径_aoe1981.zip (82.04 KB, 下载次数: 9)

2020-2-29 19:47 上传

点击文件名下载附件

第四阶段附件如下（结束版）：
数独解法学习4.0_位运算优化四种基本数独技巧变动递归路径_aoe1981.zip (101.29 KB, 下载次数: 38)

2020-3-1 22:45 上传

点击文件名下载附件

（继承了版本3.0的优点，同时克服了版本3.0的弱点，本帖最佳附件（更新结束日：20200229），说明见30楼）

（补充一句：4.0版中共13个过程，其中一个是工作表事件过程；总共373行代码，“：”连接的算一行，不算起分隔作用的空行。）


（4.0版附件更新到了44楼状态，其余不再更新。）

aoe1981

附件支持复制粘贴题目，但最好使用“选择性粘贴——数值”，如下图：



对比了一下，我的附件居然比香川大侠的快一些：



当然，这是针对前面讨论过的一道题而已。

一把小刀闯天下

数独难度大点就头大，很少玩这种游戏，觉得有点枯燥

-----------
浏览器推荐使用google chrome 64位的，速度肯定没有问题，而且兼容性也非常好。edge是有很多问题，可能有点超前，但它一般带有IE11的，偶尔可以使用它。36浏览器反正我是不用的，，，

aoe1981

一把小刀闯天下 发表于 2020-2-21 20:23
数独难度大点就头大，很少玩这种游戏，觉得有点枯燥

-----------

以前一直在用，后来不支持插件了便再没用，特别是广告屏蔽插件。

vvw123

厉害👍👍👍👍，学习了

zopey

回溯法是一种数独技巧，它的逻辑是这样的：
先计算出盘面的候选数序列，然后存放到一旁等候使用。
然后从r1c1开始的第一个可能的候选数开始按从左到右、从上到下的顺序挨个试数，
下一个单元格也找出第一个可能的候选数开始试数，一直往下试数。
直到发现重复的矛盾之后，步骤回退到原始设定，可以否定它了。
然后继续从第二个数开始试数，
重复上述步骤，直到完成题目。

https://zhuanlan.zhihu.com/p/38494516

aoe1981

zopey 发表于 2020-2-21 22:13
回溯法是一种数独技巧，它的逻辑是这样的：
先计算出盘面的候选数序列，然后存放到一旁等候使用。
然后从 ...

您发的这个资料中的方法可以改造为出题方法，固定递归的顺序(1～81)，最大递归深度81层，每次均按1～9固定试数，如果把这一步变成不重复随机数，即打乱1～9的次序，(初始盘面全为0时，打乱大概81次)，算是一个正确的完整结果盘面，再挖空一些数字，做成谜题。

如果是解题的话，似乎效率低了，但好在代码简洁，也会提速。

我的代码是没有固定的递归路径的，因为每次试填一个“可填数”(不是1～9全试)后，调整4种后续缩减可填数的格子，若有“断定格”则直接填入，这直接导致后续“递归格”大量减少。

我的难度等级其实只参考了初次递归格数，我也考虑过参考递归层数更细一点划分，但太烦，后续有空了，再补充下难度等级。

aoe1981

今天调整一下我做的数独谜题难度等级，如图：



调整原因如下：

1.我以为很少能找到递归格数为64格的具有唯一解的数独谜题，没想到下面的出题网站（关于17提示数的）比比皆是：

http://163.19.32.13/~sudoku/






运行速度明显变慢，找到第一个解接近1秒，而香川大侠的则需要13秒多一些：



哈哈，原来我的算法还是很牛的（香川大侠也算熟人了，我就得意下）。

2.我碰巧遇到了一个题，将递归格数下限刷新到37格：

我坚信我的直觉判断是对的：递归格的下限虽然肯定是0（也就是不存在递归格，全是唯一格或逻辑断定格，这个我分了5级），但是当存在递归格时，下限不可能太低，因为提示格与断定格的总数越多时，剩下的格子被逻辑断定或唯一确定的可能性非常大。

目前，递归格上限64存在，下限找到了37格，我便划分为三个等级：
0~44不含0为第7级；
44~54不含44为第8级；
54~64不含54 为第9级。
第9级取了10种，第8级取了10种，第7级已知的8种：37~44，加上未知的差不多算是公平吧，以后递归格的下限被刷新了，再修改吧。

请注意：以上2~9级全是针对“唯一解”的前提讨论的。


3.下面一题是存在多个解的，号称“爆难”，见下面链接：

https://zhidao.baidu.com/question/553102634221760612.html



找到一个解还是很容易的，我用了0.5秒，香川大侠用了11秒多：




但是还没等我得意完，就出了一个问题，我试图统计解的个数，将这道题划归原先的等级1（解的个数两位数或三位数）或等级0（解的个数四位数及以上），强制结束解的个数为1000，结果程序似乎进入了死循环，半天出不了结果，我以为是我的程序的bug，便强制性结束了。于是，吓的我赶紧把原先解不唯一的由3个等级缩减为2个等级，只对解的个数为个位数的数独谜题单列一级。

后来，我排查再三，发现程序没漏洞，我设置程序断点执行时发现，有时候1个方案的确很短，比如上面的0.5秒 ，这是大多数情况，但偶尔有几次1个结果却要1到2秒（我凭感觉）。我想把这一切截图记录下来，但后来又莫名的正常，如下图：



2000个结果，也就是38秒左右。真是奇怪。

一种可能：我当时电脑的状态不够好，赶巧了，但似乎说服力不大；

更大的可能：我的代码中将各递归格按“可填数”由少到多排序，排在前面的总是2个，故而结果呈现的树状图是二叉的，这个应该没有问题，要命的是我接下来我会根据当前递归填入的空格，调整后续4种情况，这使得搜寻所有结果不见得是在同一棵“分支树”上进行的，说不定，会在遍历的某一支处出现“三叉”或更多叉也未可知。而且一个明显的现象是，有时只找一个解递归12层，当你在第5个解输出后统计结果数时，会发现输出的递归层数有可能是20层，这说明生成每个结果的用时并不是均匀的。

鉴定一个算法，可能需要更多的测试。

aoe1981

忽然间想到一个问题：根据唯一格数量（不存在递归格的情况下）划分5个难度等级也需要调整一下。

唯一格自然最少是1格，这个是很能想通的，只要在一个完整答案上挖走一格就可以了，而且这一格的可填数绝对是1个，不可能递归测试。

但是结果唯一的数独谜题的唯一格的上限理论上是64格，估计不会达到这个数，格数越少，越不容易逻辑断定所有格子（当然我说的逻辑断定是指：不能用试填数字的办法，具体指我代码中采用的同列、同行、同宫、同宫其余两列两行贯通排除断定法），故而，我猜测：60格以上的唯一格是很少见的。

我在附件中测试得到的最大唯一格数是：51格，因此，我将难度等级标准调整为：




可见，进一步扩大等级6的范围，降低门槛，为大于48，小于等于64。本级为16种情况，2、3、4、5级各为12种情况。


一个好的难度等级应当将题目均匀划分，如果出现某几个等级大概率出现，某几个等级小概率出现，这样的难度等级就是失败的。


我的难度等级也可能出现题目扎堆或凋零的情况：一是0级，包含大量解不唯一的数独谜题，极端情况是只输入一个提示数，如：



，这样的题是大量存在的，尤其对于“出题算法”一般的题目生成器而言（那个17格数独谜题全是精心生成的，基本是唯一解，测试较少），1级指解的个数在2到99之间（进一步调整下），如果只单列个位数解的话，会显得孤零零的。

二是6、7两级，6级是“唯一格”的最多极限级，7级是“递归格”的最少极限级，这两级我虽然放大了，但说不定也会孤零零的。

顶楼附件再度更新至本楼。

aoe1981

“世界最难数独”看来只是讲故事的，不过如此:

https://baike.baidu.com/item/%E4%B8%96%E7%95%8C%E6%9C%80%E9%9A%BE%E6%95%B0%E7%8B%AC/13848819?fr=aladdin




应该非人力可以设计出来吧……