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

Question

[这篇文章收视率很低，所以我提出了一些修改建议，试图为子孙后代改进它。我希望它对将来找到它的任何人都有帮助！]

我一直试图通过一个简单的数独例子来理解递归/回溯/DFS。我对数独示例本身并不感兴趣，因此根据建议，我将下面的示例最小化为一个2x2的数独板，以便只关注让我对递归感到困惑的一点（谢谢@mistermiagi的建议）

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

因此，对于输入[[0,0], [0,2]]，输出应该是[[[2,1],[1,2]]，但是我收到了输出False

@Thierrylahuille注意到了代码中的问题：在尝试了每个可能的子节点（在本例中，通过尝试两个值1和2）后，我错过了“回溯”步骤，需要添加一行，将值重置为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个的板

如果你能帮助我理解递归，我将非常感激

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

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)行，然后对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。此时，返回并返回到递增上一个方格中的值，但当前方格中仍然包含值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秒左右…）。看看this question了解有效方法的想法