12

是否有任何算法可以解决任何传统的数独难题,无需猜测?

这里的猜测是指尝试一个候选者,看看它走了多远,如果发现与猜测相矛盾,则回溯到猜测步骤并尝试另一个候选者;当所有候选人都用尽而没有成功时,回溯到上一个猜测步骤(如果有;否则拼图证明无效。)等。

EDIT1:感谢您的回复。

传统数独是指 81 盒数独,没有任何其他限制。让我们说我们知道解决方案是唯一的,是否有任何算法可以保证在不回溯的情况下解决它?回溯是一种通用工具,我没有错,但是使用通用工具解决数独会降低(手动或通过计算机)数独谜题的价值和乐趣。

人类如何解决所谓的“世界上最难的数独”,他需要猜测吗?

我听说一些研究人员偶然发现他们的一些数据分析算法可以解决所有数独问题。这是真的吗,他们也必须猜测吗?

4

4 回答 4

3

您可以使用人类用来解决数独的技术。只需跟踪每个方格中的每个可能数字,如果只有一种可能性,则放置一个数字。不断更新可能性,直到数独解决。您可以通过使用规则或使用一些更复杂的推理来排除可能性。例如,如果在一行中有两个方格具有可能性 1 和 2,则该行中的所有其他方格都不能是 1 或 2。

但是,请记住,并非每个数独都有唯一的解决方案,也不是每个数独都可以用这种方法解决。

编辑:可以在这里找到更复杂的人类技术:

http://www.sudokudragon.com/sudokustrategy.htm

于 2011-08-21T00:16:46.950 回答
2

不是一个可靠的答案,仅供参考:

有一个在线数独求解器,使用以下策略像人(而不是计算机)一样解决问题。

1:隐藏单打
2:裸对/三联
3:隐藏对/三联
4:裸四联
5:指向对
6:盒子/线减少
艰难策略 ==========
7:X-Wing
8:简单着色
9:Y 翼
10:剑鱼
11:XYZ 翼
恶魔策略 ==========
12:X 循环
13:XY 链
14:3D 美杜莎
15:果冻鱼
16:独特的矩形
17:扩展的唯一矩形。
18:隐藏的唯一矩形
19:WXYZ 翼
20:对齐对排除
极端策略 ==========
21:分组 X 循环
22:空矩形
23:鳍状 X 翼
24:鳍状剑鱼
25:交替。推理链
26:Sue-de-Coq
27:数字强制链
28:Nishio 强制链
29:单元强制链
30:单位强制链
31:几乎锁定的集合
32:死亡开花
33:图案叠加方法
34:四边强制链
“试用和错误” ==========
35:鲍曼的宾果游戏

我通过导入从 Android 数独应用程序的“非常难”级别挑选的数独来尝试它,我在该应用程序上坚持了很长时间。求解器解决了,使用的最先进的策略是“3D Medusa”,非常令人印象深刻。

关于最后一个策略,

Bowman's Bingo 并不能解决所有“分叉”数独游戏,但如果彻底应用,它将破解 80% 以上的数独游戏。它不像 Tableling 或 Nishio 那样是灵丹妙药,但如果你只剩下最后 20 个左右未解决的方格,它会更容易做并且效果会更好。

于 2015-06-02T02:08:12.607 回答
1

如果您只想要任何无需猜测即可工作的算法,您可以将所有传统数独及其解决方案写在一个大查找表中。您的算法将进行查找。不涉及猜测(但查找表对我来说仍然很脏)。

“[...] Jarvis/Russell 计算出本质不同(对称不同)解决方案的数量为 5,472,730,538。” (来自https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerating_essentially_different_Sudoku_solutions

于 2014-10-17T01:23:10.340 回答
0

已经发现了一种确定性的算法(即没有回溯),并保证找到所有数独问题的解决方案,但它相当复杂。

详细信息可以在这里找到:http: //www.nature.com/srep/2012/121011/srep00725/full/srep00725.html

于 2015-01-29T12:49:14.540 回答