java - 构建高效的数独求解器

Question

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

在程序中执行此操作的最简单方法可能是使用大量 for 循环解析每一列和每一行，收集每个单元格的可能值，然后剔除只有一种可能性的单元格(无论它们是否只包含 1数字，或者它们是其行/列中唯一包含此数字的单元格)，直到您解决了难题。当然，光是想到这个 Action 就应该在每个程序员的脑海中竖起一面红旗。

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

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

如果有人能提供解决数独谜题的循序渐进、高效的思维过程(无论是通过人还是计算机)，我将非常高兴 :)。我正在寻找一些模糊的东西(所以这是一个挑战)，但信息量足够(所以我不会完全迷失)让我开始。

非常感谢，

贾斯蒂安迈耶

编辑:

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

编辑:

没关系。我要使用 3D 阵列。

Answer 1

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

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

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

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

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