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

aoe1981

yangyangzhifeng 发表于 2020-2-24 08:13
建议每格的候选数用二进制数字表示来缓存，511表示1~9，1-1，2-2，3-4，4-8，5-16，6-32，7-64，8-128，9-2 ...

入一行比海深，最近看了一些资料，尤其同“小向标准数独技巧”（只看了前几篇），感觉自己串错门了……

您是高人，感谢指点。我只是利用了一些闲暇时间而已，见笑了。

yangyangzhifeng

aoe1981 发表于 2020-2-24 10:01
入一行比海深，最近看了一些资料，尤其同“小向标准数独技巧”（只看了前几篇），感觉自己串错门了……
...

您太谦虚，太客气了，都是爱好而已，我也是业余爱好而已，是从VBA开始起步的，后来慢慢学了VB6, 现在转向学习FreeBasic，只是消遣。如有觉得冒犯，还望海涵，若想学习FreeBasic， 推荐国人开发的IDE：Visual FreeBasic, FB号称有VB6的语法，C语言的效率

lsdongjh

数独的解法其实就是 树，只能是深度优先的搜索，然后就只剩下 代码的组织方式了。只有尝试过，才能真正理解一些算法的核心思想

aoe1981

根据20楼大神yangyangzhifeng的建议，采用位运算优化了代码，效果如下：

（1）测试下面链接22楼：

http://club.excelhome.net/forum. ... 677&pid=7258504




（2）测试下面链接26楼：

http://club.excelhome.net/forum. ... 677&pid=7258591




（3）测试下面链接29楼：

http://club.excelhome.net/forum. ... 677&pid=7258975




（4）测试下面链接36楼：

http://club.excelhome.net/forum. ... 677&pid=7261804




包括前帖讨论过的几组经典数独谜题，较原来附件提速：40%~70%不等，收效显著。

但是不敢自夸，标杆是19楼大神zopey的作品。大神yangyangzhifeng的附件我都下载了，无奈win10并不能成功运行。

我还想进一步优化，因为越研究越感觉不足很多，比如：想加入行排除、列排除，无奈测试很久，总是出现逻辑错误，主要还是对数独规则先后施加的彼此影响没有研究清楚，只好暂时作罢。顶楼更新第二阶段附件，第一阶段附件保留，供对比。

yangyangzhifeng

aoe1981 发表于 2020-2-25 18:31
根据20楼大神yangyangzhifeng的建议，采用位运算优化了代码，效果如下：

（1）测试下面链接 ...

1.用隐式唯一数/显示唯一数，直接出数
2.区块删候选数
3.猜
1-2-3-1这样周而复始，只有猜的位置需要递归，优化到毫秒级应该没有问题
http://club.excelhome.net/thread-1522472-1-1.html 这个是特殊数据结构+纯位运算的，可以看看，打扰了

aoe1981

今天打算吹吹牛了：数独解法学习3.0版发布了。
这一版如同顶楼附件名所概括的一样，主要有三个特点：

1.位运算优化；

2.四种基本数独技巧（唯余法、宫排除、行排除、列排除）完全实现；

3.固定递归路径。


我本来自诩每次按候选数个数从少到多排序后，进行变动的递归路径的算法是优异的，然而事实上，有效利用各种数独技巧才是更重要的。曾经有人说过：只要利用好四种基本的数独技巧，程序运行效率就会很高，更别说什么区块、数组、链等高级的数独技巧，今日看来，果不其然。下面几张图是对比：

本帖12楼谜题：



本帖13楼谜题：



本帖15楼谜题（不再依赖搜索顺序的不同选择）：

从小到大：



从大到小：




至此，算是给自己的能力一个自我满意的交待了。

在此，再次向大神yangyangzhifeng表示感谢，他的几条精到的建议对我帮助很大，通过实践我才得以理解其中的基础部分。因此，本帖附件事实上还存在优化空间，就先放一放了，顶楼附件追加更新。

aoe1981

补充一个版本3.0的后续测试：
对于盘面提示数少于17个的，肯定是无解或多解，大神zopey在19楼的附件直接排除这种情况，我的附件是没有的。

像下面构造的极端情况：提示数只有一个（或少于10个左右吧），版本3完全是无能的，版本1和2可以轻松应对，如图：

版本2：


版本3：



现在我寻思是不是将两个版本合并起来，根据提示数10个为分界，小于10个用版本2，大于10个用版本3？

呵呵，真够折腾！

一个有意思的现象，我在写版本3的程序时预料到了：我认为将候选数从少到多排序后递归的路径，试填正确的几率会大幅提高，一定情况下，这种处理办法是很有效果的。鱼和熊掌不能得兼，我却还惦记着二着共存。比起在版本3中反复排序、还原，我相信大多数情况下是得不偿失的。不过，首次选择候选数最少的格子作为递归的开始，还是很轻松的，下面构造的题目就是例子：

普通从1（r1c1）开始递归：



从40（r5c4）开始递归：




就这一个小小的变化，带来本质的变化，可以设想，每一步递归都选当前候选数最少的，是多么优异的选择！！！

这算是版本3后面微调的一个方向。

zopey

请参考：
每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

aoe1981

zopey 发表于 2020-2-28 14:40
请参考：
每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合 ...

如果将数独当作一种数字推理游戏，应当满足“有解且只有唯一解”的前提条件，这也算是对游戏参与者的尊重。如果只是当作一个数学问题，试图暴力分析获得一些辅助验证，应当面向更一般的情况。

aoe1981

今天应该是最后发帖了，不敢说最后一帖，但对于数独研究绝对要结束了，一是我不打算学习那些高级数独技巧了，二是我的附件4.0版终于完成了，它继承了3.0版的优点，同时又克服了3.0版在“固定递归路径”时产生的缺点，可以轻松应对已知所有情况：




13楼那道我用版本1、2跑了20多秒的题：





较之版本3，速度下降一丢丢，几乎没有影响。

15楼那道变形谜题，曾经让我的版本1、2分别跑240多秒、120多秒，现在仍和版本3一样高效：





好了，终于可以心满意足地说拜拜了……

顶楼附件会同更新。