时间戳

首页 > 解决方案 > 试图理解递归/回溯，简单不雅的数独示例

python - 试图理解递归/回溯，简单不雅的数独示例

问题描述

[这篇文章反响不佳，因此我提出了一些建议的修改，以尝试改进它以供后代使用。希望对以后发现它的人有所帮助！]

我一直在尝试使用一个简单的数独示例来理解递归/回溯/DFS。我对数独示例本身并不感兴趣，因此根据建议，我已将下面的示例最小化为仅 2x2 数独板，以便专注于让我对递归感到困惑的点（感谢@MisterMiyagi 的建议）。

在下面的代码中，我有一个辅助函数check_board，它接受一个 2x2 矩阵并检查是否有任何数字在其行和列中重复（即检查输入的 2x2 数独是否有效）。然后该函数solve_sudoku就是我所理解的标准 DFS/回溯算法，通过选择第一个空位置（由 0 表示）并尝试其中的值 1 和 2，递归地寻找解决方案来解决数独问题。

所以输入[[0,0], [0,2]]输出应该是[[[2,1],[1,2]]，但我正在接收输出False。

@ThierryLathuille 通过注意到代码中的问题来提供帮助：在尝试了每个可能的后代节点之后（在这种情况下，通过尝试两个值 1、2），我错过了“回溯”步骤，需要添加一行将值重置为 0 ，这意味着对于所有后续调用，矩阵中的正方形将停留在 2 中（或者，在最初的 9x9 示例中，停留在 9 处）：

当你看到你在方块中尝试的最后一个值不能导致有效的解决方案时，你尝试下一个，直到你达到 9。此时，你返回并返回增加前一个方块中的值，但是您当前的仍然包含值 9，因此它被认为不可用于下一次尝试。

您只需在返回之前将其恢复为原始值 0：

现在这就是我仍然感到困惑的地方和问题的重点：我试图像一棵树一样思考递归。一旦其中一个节点尝试了正方形的每个值并且它的后代节点都回来了False，它不只是False向其父节点报告吗？为什么其他人会再次用 2 看那个板？

如果您能帮助我理解递归，我将不胜感激！

编辑：@ThierryLathuille 在评论中再次回答了这个问题！非常感谢！

请注意，当递归调用您的函数时，您不会传递板的副本，而只会在任何地方操作同一个板。当您的代码运行时，每次您探索树的一个分支时，您在探索过程中触及的所有方块都留下一个非零值，因此它们不再被视为空闲。

我有一个错误的想法，即每当以递归方式调用函数时，它都会获取所有变量的新副本以进行操作。它当然可以，但不是输入！对代码的另一个修复是使用 Python 的copy模块和该行copy_board = copy.deepcopy(board)并在函数的每个实例化时操作并返回copy_board，这是我错误地认为 Python 总是在递归中所做的。

也许这与按值传递与按引用传递有关，而 Python 总是按引用传递？关于这个主题的任何更多讨论仍然值得赞赏！

这是带有修复它的行的损坏代码注释掉：

def check_board(board: list):
    for i in chars:
        for j in chars:
            for k in chars:
                if k == j:
                    continue
                if board[i][j] == board[i][k] and board[i][j] != 0:
                    return False
                if board[j][i] == board[k][i] and board[j][i] != 0:
                    return False
    return True

def solve_sudoku(board: list):
    chars = range(2)
    if not check_board(board):
        return False
    for i in chars:
        for j in chars:
            if board[i][j] == 0:
                for a in chars:
                    board[i][j] = a+1
                    if solve_sudoku(board):
                        return solve_sudoku(board)
                # uncommenting this next line fixes the algorithm
                #board[i][j] = 0
                return False
    return board


board = [[0,0],[0,2]]

if __name__ == "__main__":
    print(solve_sudoku(board))

输出： False

标签： pythonrecursiondepth-first-searchbacktrackingsudoku

解决方案

当你看到你在方块中尝试的最后一个值不能导致有效的解决方案时，你尝试下一个，直到你达到 9。此时，你返回并返回增加前一个方块中的值，但是您当前的仍然包含值 9，因此它被认为不可用于下一次尝试。

您只需在返回之前将其恢复为原始值 0：

if board[3*a+c][3*b+d] == board[3*a+e][3*b+f] and board[3*a+c][3*b+d] != 0:
    board[i][j] = 0
    return False

输出：

[[4, 8, 6, 9, 1, 5, 7, 3, 2], 
 [7, 2, 5, 4, 6, 3, 1, 9, 8],
 [3, 9, 1, 7, 8, 2, 4, 5, 6], 
 [5, 6, 4, 1, 9, 7, 2, 8, 3],
 [9, 7, 3, 6, 2, 8, 5, 1, 4],
 [8, 1, 2, 5, 3, 4, 6, 7, 9],
 [2, 5, 7, 8, 4, 9, 3, 6, 1], 
 [1, 3, 8, 2, 5, 6, 9, 4, 7],
 [6, 4, 9, 3, 7, 1, 8, 2, 5]]

这是正确的答案。

但是，它需要很长时间才能到达它（大约 30 秒左右......），因为代码的很多部分，尤其是检查行/列/块中是否存在重复项的效率非常低。看看这个问题，了解有效方法的想法。

推荐阅读