这段代码是如何工作的？回溯和递归

Question

这是解决数独的工作代码：

def is_valid(board, row, col, num):
    for i in range(9):
        if board[row][i] == num:
            return False

    for i in range(9):
        if board[i][col] == num:
            return False

    box_row = (row - row % 3)
    box_col = (col - col % 3)

    for i in range(3):
        for j in range(3):
            if board[box_row + i][box_col + j] == num:
                return False
    return True

def solve(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1,10):
                    if is_valid(board, row, col, num):
                        board[row][col] = num
                        solve(board)
                        board[row][col] = 0

                return False

print(np.matrix(board))

solve(board)

让我感到困惑的部分是：

if board[row][col] == 0:
    for num in range(1,10):
        if is_valid(board, row, col, num):
            board[row][col] = num
            solve(board)
            board[row][col] = 0

    return False

这部分是如何工作的？我知道它会将数字分配给当前行和列然后，运行 solve() 函数再次出现，所以，程序什么时候会运行 this:

board[row][col] = 0

因为据我了解，除非已经有 0，否则代码不会运行。然后程序将检查该号码是否有效。另外，如果没有有效的 num [1~9]，会不会 return false 并退出函数？

谈论它让我头晕目眩，我知道这甚至很难解释，我用谷歌搜索了一下。

编辑：

这是我正在处理的董事会：

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

输出：

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

Answer 1

solve函数return有两种情况。我将重写代码以使其更甜美（但你的也可以）*:

def solve(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1,10):
                    if is_valid(board, row, col, num):
                        board[row][col] = num
                        solve(board)
                        board[row][col] = 0

                return False
    return True

因此，只要 solve 方法到达其中一个 return 语句，它就会 return 调用它的方法。请注意，在调用 solve 之外有两个 if 语句。这些可以评估为 False。如果他们经常评估 False，就会达到 return 语句之一。这就是你如何到达 board[row][col] = 0

如果你想看到解决的数独，你也必须在最后调用 solve 之后重复 print(np.matrix(board))。

*旁注：

如您所写，solve 方法可以 return None 或 False，这是不好的风格，因为 bool(None) 的计算结果也是 False。为什么是returnNone？那是因为函数末尾的 return 语句不等同于 return None.
除非以后需要 True/False，否则您也可以只使用 return。那是因为 solve(board) 没有分配给任何东西。
如果数独没有解决方案，您将进入一个复杂的无限循环，只有在达到最大递归深度（在 CPython 中）时才会结束。

Answer 2

假设（在撰写本文时）问题中的代码存在缩进错误，求解器如下所示：

def solve(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                # ignore the code here for now

                return False

    print(np.matrix(board))

暂时忽略我用注释替换的代码是做什么的，这个函数做的是拿一块板子，遍历每一个方块，如果有一个为0，returnFalse，否则打印电路板。

即如果board已经解决了，打印出来，如果没有解决，return False.

False 是 return 的事实无关紧要；它也可能只是 return.

所以，对于被注释掉的代码。这样做是针对找到的每个 0，尝试用每个有效数字替换它，然后递归地尝试解决这个问题。

        if board[row][col] == 0:
            for num in range(1,10):
                if is_valid(board, row, col, num):
                    board[row][col] = num
                    solve(board)
                    board[row][col] = 0

所以，如果它是板上唯一的 0，那么如果它找到一个有效数字，调用 solve 将导致板被打印出来。

如果没有有效数字，那么在某个时候插入板的数字之一是不正确的；我们不递归调用 solve，只是继续 return.

因此，对 solve 的递归调用可能会或可能不会找到有效的解决方案，代码不会假设只有一个解决方案存在，并且在任何一种情况下都会继续寻找。它需要撤消它所做的事情，因为它仅在先前递归调用选择的上下文中有效。因此将正方形设置回 0。

这段代码是如何工作的？回溯和递归

how is this code working? backtracking and recursion

python

recursion

backtracking

recursive-backtracking