试图理解recursion/backtracking，简单粗暴的数独例子

Question

[此 post 反响不佳，因此我提出了一些建议的修改，以尝试改进它 post 的真实性。希望对以后找到的人有所帮助！]

我一直在尝试通过一个简单的数独游戏示例来理解 recursion/backtracking/DFS。我对数独示例本身并不真正感兴趣，所以根据建议，我将下面的示例最小化为 2x2 数独板，以便只关注递归让我感到困惑的地方（感谢@MisterMiyagi 的建议).

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

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

@ThierryLathuille 通过注意到代码中的问题来提供帮助：在尝试了每个可能的后代节点之后（在本例中，通过尝试两个值 1、2），我错过了 "backtracking" 步骤，需要添加一行将值重置为 0，这意味着对于所有后续调用，矩阵中的方块将停留在 2（或者，在原始 9x9 示例中，停留在 9）：

When you see that the last value you tried in a square can't lead to a valid solution, you try the next one, until you reach 9. At this point, you return and go back to incrementing the value in the previous square, but you current one still contains the value 9, so it is considered as non available for the next attempts.

You just have to put it back to its original value of 0 before returning:

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

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

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

Note that when calling your function recursively, you don't pass copies of the board, but only manipulate the same board everywhere. As your code worked, each time you explored a branch of the tree, all the squares you touched during the exploration were left with a non-zero value, so they were not considered as free any more.

我有一个错误的想法，即每当以递归方式调用函数时，它都会获得其所有变量的新副本以进行操作。当然可以，但不是输入！代码的另一个修复是使用 Python 的 copy 模块和行 copy_board = copy.deepcopy(board) 并在函数的每个实例化时对 return 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

Answer 1

当您发现您在方块中尝试的最后一个值无法得出有效的解决方案时，您会尝试下一个，直到达到 9。此时，您 return 并返回增加前一个方块中的值，但您当前的方块中仍然包含值 9，因此它被认为不可用于下一次尝试。

您只需要在 returning:

之前将其恢复为原始值 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 秒左右...）需要很长时间才能到达它，因为代码的很多部分，尤其是检查 rows/colums/blocks 中是否存在重复项效率很低。查看 this question 了解有效方法的想法。

试图理解recursion/backtracking，简单粗暴的数独例子

Trying to understand recursion/backtracking, simple inelegant Sudoku example

python

recursion

sudoku

backtracking

depth-first-search