Python嵌套函数中无法保存数独棋盘状态到全局数组的问题

问题描述 #

我写了一个Python数独求解程序，想把所有有效解保存到数组并返回，但没成功。程序逻辑能正常执行，但solver函数的两处嵌套else分支里，没法把当前棋盘状态保存到allAns数组，每次存的都是初始带点的棋盘。试过用nonlocal变量、把allAns作为参数传入等方法都没解决，求帮助。

原程序代码：

def solveSudoku(board: list[list[str]]) -> None:
    allAns = []
    board1 = board.copy()
    def totalEle(i: int, j: int, allEle: list[int]):
        for b in range(9):
            if board[i][b] != '.':
                allEle[int(board[i][b]) - 1] = False
            if board[b][j] != '.':
                allEle[int(board[b][j]) - 1] = False
            boxI = (i // 3) * 3 + b // 3
            boxJ = (j // 3) * 3 + b % 3
            if board[boxI][boxJ] != '.':
                allEle[int(board[boxI][boxJ]) - 1] = False

    def solver(i: int, j: int):
        if board[i][j] == '.':
            cannotBe = [True for _ in range(9)]
            totalEle(i, j, cannotBe)
            for k in range(1, 10):
                if cannotBe[k-1]:
                    board[i][j] = str(k)
                    if j < 8:
                        solver(i, j + 1)
                    elif i < 8:
                        solver(i + 1, 0)
                    else:
                        for m in range(9):
                            for n in range(9):
                                board1[m][n] = board[m][n]
                        allAns.append(board1)
                    board[i][j] = '.'
        else:
            if j < 8:
                solver(i, j + 1)
            elif i < 8:
                solver(i + 1, 0)
            else:
                for m in range(9):
                    for n in range(9):
                        board1[m][n] = board[m][n]
                allAns.append(board1)
    solver(0, 0)
    print(allAns)
    return allAns

sudoku =   [["5","3",".",".","7",".",".",".","."],
            ["6",".",".","1","9","5",".",".","."],
            [".","9","8",".",".",".",".","6","."],
            ["8",".",".",".","6",".",".",".","3"],
            ["4",".",".","8",".","3",".",".","1"],
            ["7",".",".",".","2",".",".",".","6"],
            [".","6",".",".",".",".","2","8","."],
            [".",".",".","4","1","9",".",".","5"],
            [".",".",".",".","8",".",".","7","9"]]

allAnswers = solveSudoku(sudoku)

问题原因 #

核心问题是列表引用复用：

• board1 = board.copy()是浅拷贝，且全程复用同一个board1对象。每次找到解时，你只是把当前board的值复制到board1，再将board1的引用添加到allAns中，但allAns里的所有元素其实都指向同一个board1对象。
• 回溯过程中，你会修改board的值（填数后再改回.），board1会被反复覆盖，最终回溯完成后board回到初始状态，board1也同步变成初始状态，导致allAns里的所有元素看起来都是初始棋盘。

解决方案 #

每次找到完整解时，创建当前棋盘的深拷贝（独立的二维列表对象），再添加到allAns中，避免引用复用。无需额外的board1变量，直接用列表推导式生成新的棋盘副本。

修改后的代码 #

def solveSudoku(board: list[list[str]]) -> list[list[list[str]]]:
    allAns = []

    def totalEle(i: int, j: int, allEle: list[bool]):
        for b in range(9):
            if board[i][b] != '.':
                allEle[int(board[i][b]) - 1] = False
            if board[b][j] != '.':
                allEle[int(board[b][j]) - 1] = False
            boxI = (i // 3) * 3 + b // 3
            boxJ = (j // 3) * 3 + b % 3
            if board[boxI][boxJ] != '.':
                allEle[int(board[boxI][boxJ]) - 1] = False

    def solver(i: int, j: int):
        if board[i][j] == '.':
            cannotBe = [True for _ in range(9)]
            totalEle(i, j, cannotBe)
            for k in range(1, 10):
                if cannotBe[k-1]:
                    board[i][j] = str(k)
                    if j < 8:
                        solver(i, j + 1)
                    elif i < 8:
                        solver(i + 1, 0)
                    else:
                        # 深拷贝当前棋盘，生成独立对象
                        allAns.append([row.copy() for row in board])
                    board[i][j] = '.'
        else:
            if j < 8:
                solver(i, j + 1)
            elif i < 8:
                solver(i + 1, 0)
            else:
                # 深拷贝当前棋盘，生成独立对象
                allAns.append([row.copy() for row in board])
    solver(0, 0)
    print(allAns)
    return allAns

sudoku =   [["5","3",".",".","7",".",".",".","."],
            ["6",".",".","1","9","5",".",".","."],
            [".","9","8",".",".",".",".","6","."],
            ["8",".",".",".","6",".",".",".","3"],
            ["4",".",".","8",".","3",".",".","1"],
            ["7",".",".",".","2",".",".",".","6"],
            [".","6",".",".",".",".","2","8","."],
            [".",".",".","4","1","9",".",".","5"],
            [".",".",".",".","8",".",".","7","9"]]

allAnswers = solveSudoku(sudoku)

补充说明 #

• 把返回类型标注从None改成了list[list[list[str]]]，更符合实际返回值的类型。
• [row.copy() for row in board]会为每一行创建新列表，生成完全独立的棋盘副本，后续的回溯修改不会影响已经存入allAns的解。

内容的提问来源于stack exchange，提问作者Aayush Gupta