优化数独求解

yynrzwh · 发表于 2024-8-23 17:36

数独递归求解优化了一下，忍不住和大家分享下。

网上号称最难数独题0.3秒可解。

朋友们有难的数独题可以测试一下。

数独求解.zip (29.82 KB, 下载次数: 40)

扇扇扇 · 发表于 2024-8-23 18:55

留个记号

jx928867128 · 发表于 2024-8-24 20:20

老师您太强大了

micch · 发表于 2024-8-24 23:23

分享一下算法思路？用的什么算法

micch · 发表于 2024-8-25 10:03

模拟人工解题，代码可以实现纵横格相互限制的唯一性判断，用坐标位置举例：（1,1）点是5，（2,4）点也是5，那么（3,7）（3,8）（3,9）必然有一个5，并且（1,789）（2,789）直接排除5，这种模式。然后代码每次判断都根据优先级判断做唯一值判断和排除。

这样不用递归去判断再回溯，每一步都判断出一个结果，直到全部结果。这种思路是否可行，会不会比回溯更快？

yynrzwh · 发表于 2024-8-25 10:10

micch 发表于 2024-8-24 23:23
分享一下算法思路？用的什么算法

还是用递归，以前发的https://club.excelhome.net/thread-1092452-5-1.html
遍历数组，每个空格从1-9试填，9个数字都不能填则回溯。

本次优化主要是使用attack数组判断数字能否使用。
attack(1-9,1-9,1-9)一维二维对应的是源数组坐标，第三维表示数字1-9，
数组的值为TRUE，表示该数字使用过了，不能填，反之可用。
参考了八皇后问题的解法。

以前的解法使用字典
同一题目，优化后可在1秒内，字典需要7秒左右。

yynrzwh · 发表于 2024-8-25 10:37

其实我觉得解数独不算难，出数独题目才是难题。
因为数独要求唯一解，这是难点所在。

目前我的思路是随机生成一个数组（填满数字1-9，符合数独规则）
然后随机挖空。
每挖一个，就判断一次是否有唯一解。
方法有点笨，相当于解了N次数独题

兄弟们有没有更好的方法？

挖50个以上就有点慢了，
55个很慢，60个以上基本不可能。

注意，最多只能挖64个，因为最少要保留17个数字，
才能有唯一解。

zxsea_7426 · 发表于 2024-8-25 10:49

算来算去就一种结果？

yynrzwh · 发表于 2024-8-25 10:50

micch 发表于 2024-8-25 10:03
模拟人工解题，代码可以实现纵横格相互限制的唯一性判断，用坐标位置举例：（1,1）点是5，（2,4）点也是5， ...

我认为回溯是不可避免的。
因为难的数独题，都不能根据规则直接得出唯一数字。
可填数字有多个就要试，试错了就要回溯。
有差别的是，要试的数字多少而已。

另外，模拟人工高阶解法是很难的，反正我觉得挺难。

yynrzwh · 发表于 2024-8-25 10:52

zxsea_7426 发表于 2024-8-25 10:49
算来算去就一种结果？

你这只有一个数字也不是数独啊

		自动登录	找回密码
密码			免费注册

[分享] 优化数独求解