N皇后问题Python回溯解法输出异常：为何结果全为0？

我在解决N皇后问题时，编写了递归回溯解法，但遇到一个奇怪的问题：当所有皇后放置完成后直接将board添加到结果列表ans，最终输出的所有解都是全0的棋盘；但逐元素复制board的内容到ans后，代码就能正常输出正确结果。

错误代码（输出全0） #

def isSafe(board,row,col):
    for i in range(row):
        if board[i][col]==1:
            return False
        
    x,y = row,col
    while x>=0 and y>=0:
        if board[x][y]==1:
            return False
        x-=1
        y-=1

    x,y = row,col
    while x>=0 and y<len(board):
        if board[x][y]==1:
            return False
        x-=1
        y+=1

    return True
        
        
def solveNQueens(n):
    ans = []
    def placeQueens(board,row):
        if row==len(board):
            ans.append(board)  # 直接添加board引用
            return

        for i in range(len(board)):
            if isSafe(board,row,i):
                board[row][i]=1
                placeQueens(board,row+1)
                board[row][i]=0  # 回溯时修改原board
        return
                
        
    board = [[0 for i in range(n)] for j in range(n)]
    placeQueens(board,0)
    print(ans) 

solveNQueens(4)

预期输出：[[[0,1,0,0],[0,0,0,1],[1,0,0,0],[0,0,1,0]],[[0,0,1,0],[1,0,0,0],[0,0,0,1],[0,1,0,0]]]
实际输出：[[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]],[[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]]

正确代码（逐元素复制） #

def isSafe(board,row,col):
    for i in range(row):
        if board[i][col]==1:
            return False
        
    x,y = row,col
    while x>=0 and y>=0:
        if board[x][y]==1:
            return False
        x-=1
        y-=1

    x,y = row,col
    while x>=0 and y<len(board):
        if board[x][y]==1:
            return False
        x-=1
        y+=1

    return True
        
        
def solveNQueens(n):
    ans = []
    def placeQueens(board,row):
        if row==len(board):
            ans.append([])
            for i in range(len(board)):
                ans[-1].append([])
                for j in board[i]:
                    ans[-1][-1].append(j)  # 逐元素复制内容
            return

        for i in range(len(board)):
            if isSafe(board,row,i):
                board[row][i]=1
                placeQueens(board,row+1)
                board[row][i]=0
        return
                
        
    board = [[0 for i in range(n)] for j in range(n)]
    placeQueens(board,0)
    print(ans)

solveNQueens(4)

问题原因 #

这是Python中可变对象引用的特性导致的：

• 列表是可变对象，当你执行ans.append(board)时，并没有把当前棋盘的内容复制到ans里，而是把board这个列表对象的引用添加到了ans中。
• 回溯过程中，后续的board[row][i]=0操作会直接修改这个唯一的board对象的内容。当所有递归结束后，board已经被完全清空（所有位置变回0），而ans里的所有元素都是指向这个被清空的board的引用，所以最终输出全是0。
• 第二段代码通过逐元素创建新列表，相当于生成了当前board的深拷贝，每个解都是独立的新对象，不会被后续的回溯操作修改，因此能保存正确的结果。

更简洁的正确写法 #

不需要逐元素循环复制，可以用列表推导式快速生成棋盘的副本：

def isSafe(board,row,col):
    for i in range(row):
        if board[i][col]==1:
            return False
        
    x,y = row,col
    while x>=0 and y>=0:
        if board[x][y]==1:
            return False
        x-=1
        y-=1

    x,y = row,col
    while x>=0 and y<len(board):
        if board[x][y]==1:
            return False
        x-=1
        y+=1

    return True
        
        
def solveNQueens(n):
    ans = []
    def placeQueens(board,row):
        if row==len(board):
            ans.append([row.copy() for row in board])  # 生成每个行的副本，组成新棋盘
            return

        for i in range(len(board)):
            if isSafe(board,row,i):
                board[row][i]=1
                placeQueens(board,row+1)
                board[row][i]=0
        return
                
        
    board = [[0 for i in range(n)] for j in range(n)]
    placeQueens(board,0)
    print(ans) 

solveNQueens(4)

内容的提问来源于Stack Exchange，提问作者Sanjit Jha