具有暴力回溯错误的Python Sudoku递归

Question

我做功课一道数独题求解,但我遇到了一些困难.该代码现在周期过去的解决方案,虽然它确实达到它容易难题,并为困难的难题,它卡住几个9的没有明显的原因.我将不胜感激任何帮助.(check_cell确定放置是否有效.)

1. 是回溯这段代码正确实施,如果没有,怎么会缝？
2. 如何阻止求解器冻结？它解决了约3行,然后冻结,改变大部分值至787-9.

一些代码:

def solve_helper(self, row, col):
# Try placing a number in each column of current row
    board = self.the_board
    if board[row][col] != 0:
        ?????
    elif board[row][col] == 0:
        for i in range(1,10):
            print("Setting value at i with ") + str (i) + (" located at " ) + str(row) + str(col)
            self.set_cell(row, col, i)
            self.guesses = self.guesses + 1
            if self.check_cell(row, col):
                if self.solve_helper(row, col): return True
            else:
                self.set_cell(row, col, 0)
    else:
        return self.mover(row,col)
    return False

def mover(self, row, col):
    if col + 1 != 9:
        return self.solve_helper(row, (col+1))
    elif row + 1 != 9:
        print "Moving to row" + str(row + 1)
        return self.solve_helper((row+1),0)
    else:
        print "SOLUTION FOUND"
        return True

Answer 1

您遇到的麻烦是，某些递归调用没有正确返回结果，因此当找到您的解决方案时，它会被遗忘在递归堆栈的几层中。这是您需要的第一个修复，添加return到中进行的递归调用mover：

def mover(self, row, col):
    if col + 1 != 9:
        return self.solve_helper(row, (col+1))  # added return
    elif row + 1 != 9:
        print "Moving to row" + str(row + 1)
        return self.solve_helper((row+1),0)     # here too
    else:
        print "SOLUTION FOUND"
        return True

solve_helper在跳过预先解决的单元格的函数特殊情况下，您还需要类似的东西。函数的结尾应该是：

else:
    return self.mover(row, col)  # added return
return False

编辑：

好的，我在代码中发现了更多问题。其中两个是求解器的逻辑问题，一个是显示问题，除了在求解过程中看起来很奇怪之外，不会导致任何实际问题。

问题：

1. 首先，您的最新代码已solve_helper调用自身，而不是调用mover. 这使得在移动之前需要额外的函数调用（尽管我认为它实际上可能不会破坏求解器）。
2. 其次，如果solve_helper将一个单元格设置为 9，但随后回溯到（在无法解决后面的一些单元格之后），则在进一步回溯之前，9 不会重置为零。
3. 最后，显示问题。将单元格设置为 0 不会阻止显示其旧值。这看起来很像#2 中的问题（回溯后留下了 9），但实际上这只是装饰性的。

第一个问题很容易解决。只需将呼叫更改solve_helper为mover呼叫即可。这实际上就是您在问题中放入的原始代码中的内容。直接调用solve_helper实际上不会得到错误的结果（因为solve_helper第二次会跳过已经填写的单元格），但它会为递归的每个级别添加不必要的额外函数调用。

第二个问题有点复杂，这就是您在某些板上陷入困境的地方。您需要做的是将执行该操作的行移出它当前所在的self.set_cell(row, col, 0)块else。事实上，如果您愿意，您实际上可以将其完全移出循环（因为只有在您在之后回溯时才真正需要它）当前单元格的所有值均不起作用）。我认为这是 for 循环的最佳安排（也将return False语句向上移动）：

for i in range(1,10):
    print("Setting value ") + str (i) + (" at " ) + str(row) + ", " + str(col)
    self.set_cell(row, col, i)
    self.guesses = self.guesses + 1
    if self.check_cell(row, col):
        if self.mover(row, col):
            return True
print "Backtracking"
self.set_cell(row, col, 0)
return False

最后，解决显示问题需要进行两项更改。首先，去掉 中的条件set_cell。您希望始终更新显示。接下来，在 中update_textfield，将调用移到块delete之外if，以便它始终发生（将 留insert在 下if）。这使得将单元格设置为零将擦除以前的值，但不会使其显示实际的 0 字符（它将不显示任何内容）。

我认为这应该可以做到。请注意，您使用的算法仍然相当慢。我通过 Google 快速搜索在互联网上找到了一个棋盘，花了 5 分钟多的时间进行了 122482 次猜测，但最终还是成功了。其他棋盘（尤其是那些在前几个空位中需要 8 或 9 的棋盘）可能需要更长的时间。