数独求解器，解决特殊情况

我正在研究一个数独求解器，递归回溯法，除了一件事情之外几乎完成了。如果我会在拼图中的某个位置放置重复项（例如顶角的1,1），它可以继续尝试寻找解决方案，尽管它不是一个可解决的难题。数独求解器，解决特殊情况

任何帮助，非常感谢！

罗布

2013-03-19 Rob

我建议逐行执行您的[调试器]（http://www.vogella.com/articles/EclipseDebugging/article.html）（或[这里]（http：//www.jetbrains。 com/idea/features/compiler.html）如果你使用的是IntelliJ）。 – 2013-03-19 15:17:05

我认为它应该是解决方法，但不完全确定如何编写它。也许另一种方法呢？对不起，我对Java很新。也许有人可以给你一段代码。但是，我的猜测是在解决方法或编写一个新的方法checkRow和checkColumn。 – Michael 2013-03-19 15:19:02

我不明白你的意思。数独谜题在每个插槽中都有一个数字，那么它是什么被复制？您是在谈论解决方案还是用户尝试解决方案的用户？请记住，这里的读者除了我们（可能）知道的数独之外没有任何背景。 – arcy 2013-03-19 15:25:59

嗯，你知道回溯的方法是，当你的拼图打一个矛盾，所以每走一步，你应该运行“验证”方法，如果让人不解的是非法行为，则您所做的最后一步是非法的。

当你发现你的举动是非法的，你可以递归地回溯并继续前进。

另外，请注意，这是相当天真的方法，也许一些数独专家有一个更好的算法，但这种蛮力应该做的伎俩。

来源

2013-03-19 15:26:26 Cruncher

如果square（1，1）被分配了错误的值，但它在当时有效。然后这个难题的其余部分将尝试从这一点解决。即使它试图做出的举动是正确的，那么很快就会出现错误，即使这种错误不对应，那么也不会这样做。 – 2013-03-19 15:46:07

虽然我不太确定我会如何实现这样的方法。 – Rob 2013-03-19 15:51:47

当时这不是问题，但它会导致问题在正确的道路上。但是当它在道路上遇到问题时，它将回溯一步，尝试新的价值观。在尝试了所有的价值观之后，他们看到了所有的价值观都会相互抵触，并回到一个层面，最终会回过头来解决最初造成矛盾的原因。 – Cruncher 2013-03-19 15:52:12

你想检测一个无效的情况，所以你应该在调用解算器之前检查它。你的求解器本身不会创建无效的解决方案...

来源

2013-03-19 15:28:40 pgras

关于重复，我会建议保留每个单元格的可能数字列表，当你试图解决一个单元格时，你会比较这个列表与匹配行，列和框，这样你将防止创建重复。有了这个，你可以解决更容易的谜题，而无需回溯。如果你卡住了，然后用回溯继续...

来源

2013-03-19 15:35:32 Basic

确认@pgras说... – Basic 2013-03-19 15:37:41

存储“可能”值列表的问题是您何时更新该列表？也就是说，当你放置数字时，你永远不知道直到拼图的结尾，不管这个数字是否属于那个数字（除非它是唯一可能的数值） – Cruncher 2013-03-19 15:43:44

@Cruncher我不知道他是从空白拼图开始的。我认为有一个难题要解决。我提到了更简单的那些，那些只有1个可能值的单元。首先，您将初始化列表，并且在求解期间，每当您输入数字时，都会更新相应行，列和框中的所有单元格。我实现了这一点，它的工作原理，但它只是我的数独求解器的第一部分，因为它只能完全解决更容易的谜题。 – Basic 2013-03-19 15:54:05

这不一定是的答案但它应该可以帮助你。我之前做过这样的事情，是一个宏观计划，它是可用的最高评分。

数独解算器可能是一个相当大的挑战。判断一个举措是否正确的唯一方法是如果它是绝对的或者稍后证明。这可能导致相当大的挑战，因为最终目标是基于当前情况和行动。这意味着你可以把它作为一个排列组合来处理。你可以通过每个方块并找出它有可能的数字。从那里，你可以得到一个或两个定义的方块。基于此，有很多可能的方法来达到终点。

解决谜题（无错误 - 每个正方形填充）或出现故障时，将定义“终点”。

基于此，您可以将每个移动视为一个节点，然后构建围绕可能移动的树状系统。

例如：

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-19 16:01:54

要实现Validate类，难道你不能在解决方法中写Validate.validate();吗？希望能帮助到你。

来源

2013-03-19 16:50:18 Michael

已经尝试过，但没有工作。 – Rob 2013-03-19 16:56:28

嗯，我认为结构是正确的，不知道你应该有哪些内部的小精灵。也许有人可以对此采取措施，因为我认为这部分是正确的。 – Michael 2013-03-19 16:59:03

数独求解器，解决特殊情况

回答

相关问题