6

是的，我知道这不是什么新鲜事，而且已经有很多问题（它甚至有自己的标签），但我想用 Java 创建一个数独求解器，只是为了训练自己编写更多的代码高效的。

在程序中执行此操作的最简单方法可能是通过大量的 for 循环解析每一列和每一行，收集每个单元格的可能值，然后以一种可能性（无论它们是否只包含 1 个数字，或者它们是行/列中唯一包含此数字的单元格），直到您解决了难题。当然，对动作的纯粹思考应该在每个程序员的脑海中升起一面红旗。

我正在寻找的是以最有效的方式解决这个傻瓜的方法（请尽量不要包含太多代码 - 我想自己弄清楚那部分）。

如果可能的话，我想避免使用数学算法——那些太容易了，而且 100% 不是我的工作。

如果有人可以提供一个逐步、有效的思维过程来解决数独难题（无论是由人还是计算机），我会非常高兴:)。我正在寻找一些模糊的东西（所以这是一个挑战），但信息量足够大（所以我并没有完全迷失）让我开始。

非常感谢，

贾斯蒂安·迈耶

编辑：

看着我的代码，我开始思考：存储这些求解状态（即数独网格）的一些可能性是什么。我想到了 2D 阵列和 3D 阵列。哪个可能是最好的？2D 可能更容易从表面管理，但 3D 阵列也会提供“盒子”/“笼子”编号。

编辑：

没关系。我将使用 3D 数组。

4

4 回答 4

1

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

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

如果您的单元格剩余不止一种可能性，请保存拼图状态，选择可能性最少的单元格，选择其中一种可能性，然后尝试解决难题。如果您选择的可能性导致谜题矛盾，请恢复已保存的谜题状态，返回单元格并选择不同的可能性。如果您选择的单元格中的任何可能性都不能解决难题，请选择可能性最少的下一个单元格。循环遍历剩余的可能性和单元格，直到您解决了难题。

尝试解决这个难题意味着搜索每一列和每一行，收集每个单元格的可能值，然后剔除只有一种可能性的单元格。当所有的细胞都被清除掉时，你就解决了这个难题。

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

于 2010-07-27T14:06:00.590 回答
1

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

因此，我从实施解决难题的基本“规则”开始，试图找到下一个实施规则，以解决上次停止的位置。最后，我被迫添加了一个蛮力递归算法，但实际上大多数谜题都没有使用它就解决了。

我写了一篇关于我的数独求解器的博文。只需阅读“算法”部分，您就会很好地了解我是如何做到的。

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

于 2010-08-09T22:52:26.027 回答
1

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

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

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

于 2012-05-24T17:36:10.497 回答
0

您应该考虑将 Sudoku 问题简化为SATisfiability 问题。

这种方法可以避免你也思考mathematically更多logically关于人工智能的问题。

一步一步的目标基本上是：

* 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，我认为这对人工智能来说更具挑战性:)。

于 2015-07-29T14:21:16.317 回答