如果发现在其中放置任何数字 1-9 的单元格将是非法移动，则解决数独难题的蛮力算法的实现将失败。
实现是用 C 语言编写的，电路板由 9x9 数组表示。求解器从 9 开始倒计时，直到达到合法数字，如果无法达到，它会在其位置输出零。
零也表示要填充的单元格。如果输入一串零（空板），则为输出（截断）：
9 8 7 6 5 4 3 2 1
6 5 4 9 8 7 0 0 0
最后三个零在那里，因为之前填写的值没有改变。我怎样才能阻止求解器像这样失败？
问问题
2589 次
3 回答
2
如果您当前将在某个位置输入零，请返回到您输入数字的上一个位置并继续倒计时，直到您找到该位置的另一个值数字。
例如，在您的示例中：
9 8 7 6 5 4 3 2 1
6 5 4 9 8 7 0 0 0
与其将 0 置于 3 之下，不如返回并尝试将 6 置于 4 之下。
于 2010-07-23T17:06:20.140 回答
1
不要把每一个“举动”都当作正确的举动。例如，放置最后 7 个似乎没问题，但它使得在下一个单元格中没有留下有效的移动。因此，一旦遇到“无法移动”的情况，请返回并尝试下一个选项。迭代，你就会有你的解决方案。
当然，更好的方法是对只剩下少量选项的地方开始暴力破解；遍历所有单元格并开始暴力破解剩余选项数量最少的单元格。当从全零开始时，你最终会得到
9 8 7 6 5 4 3 2 1
6 5 4 0 0 0 0 0 0
3 2 1 0 0 0 0 0 0
这是合法的，无需回溯一次。
于 2010-07-23T17:08:46.220 回答
1
你可以通过将你的猜测压入堆栈来做到这一点。每次您最终想要输出零时，请将您的最后一个答案从板上弹出并继续计数。
因此，如果您在 (2,3) 中猜测 3，然后您正在查看 (3,3) 并达到零，请返回 (2,3) 并尝试 2，然后尝试 1，然后弹出到您的 (2 ,3) 猜测等。
于 2010-07-23T17:21:55.697 回答