如何修正深度优先数独解题？

Question

我正在尝试用Python创建一个数独解谜器，它使用depth-first“蛮力”来解决这个难题。然而，在重新编码了很多次之后，我一次又一次地遇到同样的错误。在

我会尽我最大的努力解释这个问题，因为这是我第一个与深度优先搜索相关的问题，可能是我遗漏了一些显而易见的东西。在

以下是精简代码（在不需要详细说明的地方与伪代码混合）：

def solvePuzzle(puzzle):
    <while the puzzle is still not solved>:
        <make a copy of the puzzle>
        <go through each unsolved box>: 
            <try to find the value of the box>
            <if the current solution is impossible, return to the parent branch>
        <if the copy of the puzzle is exactly the same as the puzzle now, no changes have been made, so its time to start branching into different possibilities>:      
            <pick a random box to guess the number of>
            <go through each possible value and run solvePuzzle() on that puzzle>:
                <if a solution is returned, return it>
                <else, try the next possible value>
    <return the puzzle>

这是我所能做的最简单的-抱歉，如果它仍然有点读/混淆。在

由于某些原因，即使在将程序设置为solvePuzzle（）之后，每个创建的拼图副本都会发现所有副本都是不可能的（不可能，我的意思是猜错了）。这不可能，因为每个数字都在测试中！在

Here's the full code（只有大约50行代码），以防不够清楚。在

如果有人能告诉我为什么这样做行不通，我会非常感激的。在

谢谢你！在

编辑：As promised, here's the "isSolved()" method.

Answer 1

我强烈怀疑问题就在这里：

# Go through each possibility in the branch until one solution is found
clone = deepcopy(puzzle)
values = clone[index / 9][index % 9]
for value in values:
    clone[index / 9][index % 9] = value
    branch = solvePuzzle(clone)
    # If a list is returned, it worked! Otherwise, try the next possibility
    if isinstance(branch, list):
        return branch

它会为每个候选值变异clone副本，并且在发现矛盾时不会恢复到半解决的谜题状态。试试这个：

^{pr2}$