如何展示数独解决方案的独特性

eri*_*icg 5 algorithm sudoku

给定一个未解的数独,如何证明它有唯一的解决方案?

Mar*_*ers 4

尝试找到两个解决方案。

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

这适用于简单的问题,但对于较困难的问题可能需要数小时或数天的时间。如果您需要更快的速度,可以使用许多优化。

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

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