5

给定一个未解决的数独，如何证明它有一个独特的解决方案？

4

6 回答 6

3

某些配置最终会导致非唯一的解决方案，例如：

* *  *  | * * * | * * *
* *  *  | * * * | * * *
* 12 12 | * * * | * * *
--------+-------+------
* *  *  | * * * | * * *
* *  *  | * * * | * * *
* 12 12 | * * * | * * *
--------+-------+------
* *  *  | * * * | * * *
* *  *  | * * * | * * *
* *  *  | * * * | * * *

其中 *s 可以是任何数字，并且12是这些单元格中的唯一可能性。在这种情况下，肯定会有至少两种可能的解决方案：

* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *
* 1 2 | * * * | * * *    * 2 1 | * * * | * * *
------+-------+------    ------+-------+------
* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *
* 2 1 | * * * | * * *    * 1 2 | * * * | * * *
------+-------+------    ------+-------+------
* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *

无需计算棋盘的其余部分，您就可以确定这个数独的解不是唯一的。然而，即使在某些情况下可以证明一个谜题的解不是唯一的；证明一个谜题的解决方案是唯一的唯一方法是使用蛮力来计算一组可能的解决方案只包含一个解决方案。

除了纯蛮力之外，还有一些捷径，但是在编写混合求解器时需要格外小心。大多数数独解决技术允许您找到多个解决方案（如果存在），但一些高级数独解决技术依赖于正确的数独具有唯一解决方案这一事实，并且可能导致您无法找到第二个解决方案。

于 2011-02-19T19:31:57.213 回答
3

尝试找到两个解决方案。

最简单的算法是带有回溯的蛮力递归算法。找到第一个解决方案后，回溯并寻找第二个解决方案。这很慢，但（与仅依赖逻辑的算法不同）保证最终能够找到所有解决方案。因此，如果该算法仅找到一个解决方案而终止，则该解决方案必须是唯一的。

这将适用于简单的问题，但可能需要数小时或数天才能解决更难的问题。如果您需要更高的速度，可以使用许多优化。

一个简单的优化是跟踪每个正方形的候选列表。在每一步中，找到候选人最少的方格。如果只有一个候选者，请选择该数字，更新网格和其他方块的候选者，然后继续。如果候选人数为零，您就知道您之前所做的猜测是错误的，因此您应该回溯。

更高级的优化涉及寻找允许您在不进行猜测的情况下推断数字的模式。这里有些例子：

于 2011-02-19T19:02:50.770 回答
2

Soduko 是一个包含 81 个变量的 CSP，每个框一个。使用从 A1 到 A9 的变量名称作为顶行（从左到右），使用 I1-I9 作为底行。空白框具有域 {1,2,3,4,5,6,7,8,9}，并且它们已经填充了由单个值组成的域。还有 27 个不同的约束条件“all different”，每行、列和框 9 个框一个。

您可以将 AC-3 算法用于简单的模式，或者将 PC-2 算法用于更困难的模式，但这会带来更多的计算成本。

于 2013-10-31T09:17:00.267 回答
0

在我看来，唯一的办法就是解决它。如果您能够解决它（无需猜测 - 只有 100% 的“移动”），那么这意味着它只有一个解决方案。如果您无法解决它，那么我看到的唯一方法是使用蛮力算法并检查您能够找到多少实际解决方案。

于 2011-02-19T19:05:48.013 回答
0

如上所述，可以使用带有回溯的蛮力递归算法。我想建议只向上应用两次算法；意味着候选值在搜索的过程中递增，然后使用算法向下，意味着候选值从最大可能数到1的降序检查，然后至少可以检测到两个解决方案。如果上升和下降方法的结果保持不变，那么可以说这个难题有一个独特的解决方案。

于 2019-06-10T18:23:35.757 回答
0

使用回溯技术穷尽所有可能的解决方案。如果你得到解决方案。解决方案计数器 +1。如果 counter 增加超过 1，你可以声明这个谜题有超过 1 个解并退出程序。否则，您必须等到它完成。如果 counter = 1，您确认它有一个解决方案。如果 counter = 0，则无解。

于 2021-03-12T10:55:32.063 回答