我正在研究一个带有递归回溯的数独求解器，除了一件事之外，它几乎已经完成。如果我将重复项放在谜题中的某个位置（例如顶角的 1,1），即使它不是一个可解决的谜题，它也可以一直尝试找到解决方案。
任何帮助是极大的赞赏！
抢
问问题
470 次
5 回答
2
你想检测一个无效的情况，所以你应该在调用你的求解器之前检查它。您的求解器本身不会创建无效的解决方案...
于 2013-03-19T15:28:40.373 回答
2
关于重复项，我建议为每个单元格保留一个可能的数字列表，当您尝试解决一个单元格时，您可以将此列表与匹配的行、列和框进行比较，这样您就可以防止创建重复项。有了这个，您可以解决更简单的难题而无需回溯。如果您遇到困难，请使用回溯继续...
于 2013-03-19T15:35:32.987 回答
2
你知道回溯的方式是当你的谜题遇到矛盾时，所以在每一步你都应该运行一个“验证”方法，如果谜题是非法的，那么你所做的最后一步是非法的。
当您发现您的举动是非法的时，您可以递归地回溯并继续前进。
另外，请注意，这是一种相当幼稚的方法，也许一些数独专家有更好的算法，但这种蛮力应该可以解决问题。
于 2013-03-19T15:26:26.633 回答
1
要实现 Validate 类，你不能只写Validate.validate();在你的解决方法里面吗？希望能帮助到你。
于 2013-03-19T16:50:18.220 回答
1
这不一定是答案，但它应该对您有所帮助。我以前为宏程序做过这种事情，它是可用的最高评价的。
数独求解器可能是一个相当大的挑战。判断一个动作是否正确的唯一方法是它是绝对的还是后来被证明的。这可能会导致相当大的挑战，因为结局是基于当前的情况和动作。这意味着您可以将其作为排列处理。你可以遍历每个方块并找出它有哪些可能的数字。从那里，您可以获得一两个已定义的正方形。基于此，有许多可能的方法可以到达终点。
当谜题被解决（没有错误 - 每个方块都填满）或出现错误时，将定义一个“终点”。
基于此，您可以将每个动作视为一个节点，然后围绕可能的动作构建一个树系统。
例如：
8 7 1 2 _ _ 6 9 3
2 9 6 3 8 7 1 _ _
这只是一个小例子，但基于它，分别扫描每一行，然后每一列我们可以生成可能的数字：
(5, 1) -> [4, 5]
(6, 1) -> [4, 5]
(8, 2) -> [4, 5]
(9, 2) -> [4, 5]
基于此，以及提供给我们的解决方案，我们可以看到正好有 4 种可能的解决方案：
8 7 1 2 4 5 6 9 3
2 9 6 3 8 7 1 4 5
-或者-
8 7 1 2 5 4 6 9 3
2 9 6 3 8 7 1 4 5
-或者-
8 7 1 2 4 5 6 9 3
2 9 6 3 8 7 1 5 4
-或者-
8 7 1 2 5 4 6 9 3
2 9 6 3 8 7 1 5 4
尽管这些信息不足以解决整个难题并找出哪个“正确”，但可以将其标准化并用于创建类似的系统并很快找到解决方案。
因此，您可以将所有这 4 种可能性添加到一棵树中，每个都从原始分支：
8 7 1 2 _ _ 6 9 3
2 9 6 3 8 7 1 _ _
然后递归处理它们。
希望这可以帮助！
于 2013-03-19T16:01:54.710 回答