我正在尝试使用回溯法解决 N 个皇后问题。我的解决方案是计算值，但是 return 逻辑有问题

Question

给定 n==4， Return [[[".","Q",".","."],[".",".",".","Q"],["Q","。 ",".","."],[".",".","Q","."]],[[".",".","Q","."],[ "Q",".",".","."],[".",".",".","Q"],[".","Q",".",". "]]]

这是我的代码：

        def solveNQueens(self, n: int) -> List[List[str]]:
            ans=[]
            a=[['.' for j in range(n)] for i in range(n)]
           
            def valid(row, col):
                for i in range(n):
                    if a[i][col]=='Q':
                        return False
            
                for i in range(n):
                    if (row+i<n and col+i<n):
                        if a[row+i][col+i]=='Q':
                            return False
            
                for i in range(n):
                    if (row-i>=0 and col-i>=0):
                        if a[row-i][col-i]=='Q':
                            return False
            
                for i in range(n):
                    if (row-i>=0 and col+i<n):
                        if a[row-i][col+i]=='Q':
                            return False
                for i in range(n):
                    if (row+i<n and col-i>=0):
                        if a[row+i][col-i]=='Q':
                            return False
            
                return True
            
            def solver(rowNo):
                if rowNo == n:
                    
                  
                    ans.append(list(a))
                
                    return 
                
                for i in range(n):
                    if valid(rowNo, i):
                        a[rowNo][i]='Q'
                        solver(rowNo+1)
                        a[rowNo][i]='.'
                
                return 
            solver(0)
            return ans

当我在求解器函数中每次遇到基本条件时，我都会检查它是否正确地解决了问题。但是，每次我更改 a 时，ans 变量中的附加数组都会更改引用。这导致 ans 数组包含两个附加在其初始状态完全为空的列表。我不明白为什么。请帮助我理解。

Answer 1

在行ans.append(list(a))
您正在复制一份清单，
但你应该复制其中的 8 个

因为a看起来像这样

a = [
    ['.', '.', 'Q', ...],
    [...               ],
    ...
]

您必须复制 a
的每个元素所以

ans.append([inner.copy() for inner in a])
# I also recommend to use `.copy()` instead `list(original)` to copy

我正在尝试使用回溯法解决 N 个皇后问题。我的解决方案是计算值，但是 return 逻辑有问题

I am trying to solve N queens using backtracking. My solution is calculating values, however, there is a problem with return logic

python

backtracking