构建一个高效的数独求解器

Question

是的，我知道这并不新鲜，已经有很多问题了（它甚至有自己的标签），但我想单独使用Java创建数独求解器，目的是训练自己编写更高效代码的能力。

在程序中完成这个任务最简单的方法可能是使用大量的循环遍历每一列和每一行，收集每个单元格的可能值，然后排除只有一个可能性的单元格（无论它们是否只包含一个数字，还是它们是它们所在行/列中唯一包含此数字的单元格），直到你得到一个解决的谜题。当然，程序员的头脑中应该会产生警示的想法。

我要找的是以最有效的方式解决这道难题的方法（请尽量不要包含太多代码 - 我想自己解决这部分）。

如果有人能够为解决数独难题提供一个逐步的、高效的思考过程（无论是由人还是由计算机完成），我将非常感激 : ) 。我正在寻找的是某种模糊的东西（这样才具有挑战性），但足够信息丰富（这样我就不会完全迷失方向），可以让我入门。

感谢您，Justian Meyer 编辑：

看着我的代码，我在想：存储这些解决状态（即数独网格）的一些可能性。二维数组和三维数组浮现在脑海中。哪个最好？从表面上来看，二维数组可能更容易管理，但三维数组也会提供“盒子”/“笼子”的编号。

不管了，我会使用三维数组。

- Justian Meyer

---

@wasatz：是的，我做了一些研究并找到了这个。然而，看起来很多其他人已经找到了更有效的解决方法，虽然我不想承认，但它们远远超出了我的理解水平。 - Justian Meyer

@Justian，我快速搜索了一下，并找到了一些使用“Dancing Links Algorithm”（http://en.wikipedia.org/wiki/Dancing_Links）的建议。我以前没有见过这个算法（而且我现在没有时间去深入研究它），但它看起来很有前途。也许值得一看？ :) - wasatz

在阅读非常复杂的内容之前，您可能希望先了解回溯算法(backtracking)，这对程序员通常都是有价值的（除非是Dancing Links，老实说，很多伟大的程序员实际上从未使用过）。以编程方式解决数独是回溯算法的典型示例。我有一个超快速的求解器，其递归方法只有大约12行代码。这就是递归和回溯算法的美妙之处：http://en.wikipedia.org/wiki/Backtracking - NoozNooz42

@Justian Meyer：以下是一些不错的起点：http://en.wikipedia.org/wiki/Algorithmics_of_sudoku。请注意，他们提供的所谓困难例子在3 Ghz机器上需要“45分钟才能解决”，但我的未经过优化的回溯+随机化求解器只需80秒即可解决（同时启动四个求解器，在每次旋转棋盘90度并使用随机化）。当我向我的小型求解器提供这个“困难”例子时，我笑了 :) - NoozNooz42

你有矛盾的要求：（1）简单易懂，（2）比明显的暴力方法更快。我认为你必须选择其中一个。 - finnw

Answer 1

这取决于您如何定义高效。

您可以使用暴力方法，搜索每个列和行，收集每个单元格的可能值，然后淘汰只有一个可能性的单元格。

如果仍有多个可能性的单元格，保存谜题状态，选择可能性最少的单元格，选择其中一种可能性，并尝试解决谜题。如果您选择的可能性导致谜题矛盾，请恢复保存的谜题状态，返回到该单元格并选择不同的可能性。如果您选择的单元格中没有任何可能性可以解决谜题，请选择可能性最少的下一个单元格。循环遍历剩余的可能性和单元格，直到解决谜题为止。

尝试解决谜题意味着搜索每个列和行，收集每个单元格的可能值，然后淘汰只有一个可能性的单元格。当所有单元格都被淘汰时，您已经解决了谜题。

您可以使用逻辑/数学方法，让您的代码尝试不同的策略，直到解决谜题。在Google上搜索“数独策略”以查看不同的策略。使用逻辑/数学方法，您的代码可以“解释”如何解决谜题。

- Gilbert Le Blanc

---

这是对回溯法的更好解释（感谢您），但仍然看起来有些混乱。根据您对回溯法的描述（“...并尝试解决难题...”），似乎计算机正在采取一种薄弱的统计数据，盲目地在黑暗的隧道中寻找，希望不会撞到任何东西。我能不能稍微指导一下它？ - Justian Meyer

@Justian Meyer: 不是这样的。这就是为什么它被称为蛮力方法。 你只会在最逻辑复杂的数独难题上进行很多回溯。但是你必须编写可能性的代码。 - Gilbert Le Blanc

我也预料到了 =/。我可能需要自己做一些这样的问题，以便决定何时何地应用某些策略，以获得更好的视角。 - Justian Meyer

Answer 2

当我制作我的数独求解器时，我认为我可以使用一组规则解决每个棋盘，而不需要进行任何回溯。但是这被证明是不可能的，因为即使是针对人类玩家的难题也可能需要做出一些假设。

所以我开始实现解决难题的基本“规则”，尝试找到下一个要实现的规则，以允许解决上次停止的位置。最终，我被迫添加了一个暴力递归算法，但大多数难题实际上都没有使用它来解决。

我写了一篇关于我的数独求解器的博客文章。只需阅读“算法”部分，您就可以很好地了解我是如何解决它的。

http://www.byteauthor.com/2010/08/sudoku-solver/

- Kevin Coulombe

Answer 3

如果有人需要参考Android实现，我编写了一个解决方案，使用了上面帖子中的算法。

完整的开源代码在这里：https://github.com/bizz84/SudokuSolver

此外，该解决方案从Web服务器以JSON格式加载数独谜题，并返回结果。

- bizz84

Answer 4

你应该考虑将数独问题简化为可满足性问题。

这种方法可以避免你过于数学化地思考，而更多地从逻辑上考虑人工智能。

基本的目标步骤如下：

* Find all the constraints that a Sudoku has. (line, column, box).
* Write these constraints as boolean constraints.
* Put all these constraints in a Boolean Satisfiability Problem.
* Run a SAT solver (or write your own ;) ) on this problem.
* Transform the SAT solution into the solution of the initial Sudoku.

Ivor Spence使用SAT4J完成了这项工作，您可以在此处找到他的Java Applet：http://www.cs.qub.ac.uk/~I.Spence/SuDoku/SuDoku.html。

您还可以直接从SAT4J网站下载Java代码，以查看其外观：http://sat4j.org/products.php#sudoku。

最后，这种方法的最大优势是：您可以解决N*N Sudokus，而不仅仅是传统的9*9，我认为这对于人工智能来说更具挑战性 :)

- Valentin Montmirail