具有强力回溯错误的 Python 数独递归

Question

我正在做家庭作业的数独解题器，但遇到了一些困难。现在的代码循环通过解决方案，尽管它确实会遇到简单的谜题，而对于较难的谜题，它会无缘无故地卡在几个 9 上。我将不胜感激任何帮助。 (check_cell 判断放置是否有效。)

1. 这段代码中是否正确实现了回溯，如果没有，将如何解决？
2. 如何阻止解算器卡住？它解决了大约 3 行，然后卡住，将大部分值更改为 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 block 。事实上，您可以实际上，如果您愿意，可以将它完全移出循环(因为只有当您在当前单元格的所有值都不起作用后进行回溯时，才真正需要这样做)。以下是我认为这是 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 block 之外，使其始终发生(保留 insert 在 if 下)。这使得将单元格设置为零会删除先前的值，但不会使其显示实际的 0 字符(它不会显示任何内容)。

我认为应该这样做。请注意，您使用的算法仍然很慢。求解a board I found on the internet in a quick Google search花了 122482 次猜测和超过 5 分钟，但它终于成功了。其他棋盘(尤其是那些在前几个空位需要 8 或 9 的棋盘)可能需要更长的时间。