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

aoe1981

深度资料：
“
700万小时搞定最小数独问题
sqybi
刚刚迈入 2012 年，数学界就有一个不大不小的收获。三位爱尔兰数学家发表了一篇论文，证明了数独至少需要 17 个初始数字才有唯一解。这个问题很难吗？其实一点也不，计算机才花了 700 万小时的 CPU 时间（CPU时间指CPU上执行指定代码的时钟周期数乘以每个时钟周期的时间长度）就搞定了这道数独题。这 700 万个小时它了做了什么？是三位数学家的方法很笨才导致算了这么久吗？实际上，这个时间已经不算长了。看看死理性派的详细介绍你就知道了。
”

https://www.guokr.com/article/89169/

（资料来源）

aoe1981

公平对决，这个例子我的不及香川大侠的：

8                                                               
                3        6                                       
        7                        9                2               
        5                                7                       
                                4        5        7               
                        1                                3       
                1                                        6        8
                8        5                                1       
        9                                        4               



来源：

https://baijiahao.baidu.com/s?id=1637310149410343903&wfr=spider&for=pc







测试了许多，也该歇歇了。

aoe1981

极端生猛的一道题：










不得不说，香川大侠的算法还是真的牛！

来源：
https://zhuanlan.zhihu.com/p/39306130

以及下面的网站：

http://www.cn.sudokupuzzle.org/

知乎作者给出的解题时间是25.14秒。我的电脑是amd的2400四核八线程的电脑，便宜货。

现在看来，还真不敢自吹自擂。

aoe1981

我以为只要合乎数独规则的题目，就一定有解，没成想我居然构造出了一道合乎规则但无解的题目，方法是在楼上的题目中胡乱加了一个数字：










因此，也发现了代码中一个小小的BUG，加了一句恢复事件响应的代码：

1.     If jgs = 0 Then Application.EnableEvents = True

复制代码

同步更新顶楼附件。

aoe1981

接下来的改造是在原题基础上去掉了一格，香川大侠的没问题，但却击中了我的算法的软肋：
















明天有时间了再抽空跑一跑，看来，这个谜题的结果在我的算法生成的“树”的最后部分，我再尝试一下将“可填数字”固定从小到大测试，改为随机测试，或从大到小测试，看有何变化。

zopey

aoe1981 发表于 2020-2-22 22:30
“世界最难数独”看来只是讲故事的，不过如此:

https://baike.baidu.com/item/%E4%B8%96%E7%95%8C%E6%9C ...

题目难度是 人工解题的逻辑技巧 难度，而不是暴力解题的 速度。

aoe1981

zopey 发表于 2020-2-23 09:04
题目难度是 人工解题的逻辑技巧 难度，而不是暴力解题的 速度。

言之有理，我的意思是：我觉得递归格64格的题目应当是人工解题难度最大的，自然不是将计算机暴力与人脑相提并论。说实在的，我之前都没玩过数独，前几天试着玩了一下，发现不全是逻辑推理的事，最主要的是考验人的记忆能力和数字直觉，有时我都会借助纸笔，勉勉强强只做完了两道初级版的，平均用时13分钟。

aoe1981

今天又折腾了大半天，最终处理效果如下图：





可见是增加了关于“搜索顺序”的选项。

我尝试了许多方案：

1.最先想到的是改成“从大到小”搜索，对于递归格的可填数，默认是从小到大逐个试填，既然首个结果出现极不容易，说明最终的解集中在“搜索树”的最右枝，那么只要改成“从大到小”试填，应该效率会提高，果不其然：






但我对这个处理方案不满意，虽然对结果是极满意的，因为，从大到小和从小到大一样，总会遇上让它抓狂的数独谜题，因此我想寻找折中的，或更好的方案。


2.随机试填

有：起点随机，后续从小到大，即：1~9、2~9~1、3~9~2、4~9~3、……、9~1~8；





对于这个方案，极不稳定，忽长忽短，一言以蔽之：蛇精病。

有：把排序方法改为“不稳定”的，比如在代码中增加“=”



这个方案在解决这道题目上好多了，我使用的是“不稳定冒泡排序”，使得比如：可填数都为2的空格产生了不稳定的次序，其实也是增加了“随机”和“波动”的因子。我刚想激动，却发现在普通谜题上效率又低了一些，因为，不稳定排序多了一些交换的操作。综合而言：这个方案还可以，但绝不优秀。


还有：就是一开始不再按固定的顺序从上向下、从左向右计算空格，在填入阶段就采用不同的顺序，甚至是随机的顺序，但都一个嘴脸：不稳定，蛇精病！


3.最终方案：

就让算法变得稳定一点吧，快就快，慢就慢，好歹胜过让人捉摸不定。左枝结果少了，就从右枝先找；右枝结果少了，就先从左枝找。不是很自然的处理办法吗？


其实：我实在没辙了。

顶楼附件再次更新至本楼，其中含注释掉的模块三，只作为折腾过程的辛劳备注。

zopey

1. Public Answer$
   
2. 
   
3. Sub ManualFinish_Click()
   
4.     Dim st$, i&, j&, arr, brr&(), num&
   
5.     arr = [a1].Resize(9, 9)
   
6.    
   
7.     For i = 1 To 9
   
8.     For j = 1 To 9
   
9.         If arr(i, j) = "" Then st = st & "0" Else st = st & CStr(arr(i, j))
   
10.     Next
    
11.     Next
    
12.    
    
13. num = StartNew(st)
    
14. If num = 1 Then
    
15.    ReDim brr(0 To 8, 0 To 8)
    
16.    For i = 0 To 80
    
17.        X = Int(i / 9)
    
18.        Y = i Mod 9
    
19.        brr(X, Y) = Mid(Answer, i + 1, 1)
    
20.    Next
    
21.    [m1].Resize(9, 9) = brr
    
22. Else
    
23.    MsgBox "无解或多解"
    
24. End If
    
25. End Sub
    
26. 
    
27. Function StartNew(ByVal gGame$)
    
28.     Dim sol As dlx_solver
    
29.     Set sol = New dlx_solver
    
30.    
    
31.     StartNew = sol.Solve(gGame, Answer, True)
    
32. End Function

复制代码

http://club.excelhome.net/thread-1433335-1-1.html
从中 剥离出部分功能
hello.rar (27.16 KB, 下载次数: 4)

2020-2-23 19:26 上传

点击文件名下载附件

yangyangzhifeng

建议每格的候选数用二进制数字表示来缓存，511表示1~9，1-1，2-2，3-4，4-8，5-16，6-32，7-64，8-128，9-256；这样中途计算可以采用位运算，也就不需要特意的检查步骤了，碰到有格被删空，自然是填错了