N皇后与结果状态

Question

我目前正在开发N皇后问题，我找到了一个非常接近的解决方案，但由于某种原因没有返回任何内容：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result = []
        placements = []
        self.solveNQueensR(n, 0, placements, result)
        return result
    
    def solveNQueensR(self, n: int, row: int, placements: List[str], result: List[List[str]]):
        if n == row:
            result.append(placements)
        else:
            for i in range(n):
                if self.isValid(row, i, placements):
                    placements = self.addQueen(n, i, placements)
                    self.solveNQueensR(n, row + 1, placements, result)
                    placements.pop(-1)
        return None
    
    def addQueen(self, n: int, col: int, placements: List[str]):
        string = ('.' * col) + 'Q' + ('.' * (n - col - 1))
        placements.append(string)
        return placements
    
    def isValid(self, rowToPlace: int, col: int, placements: List[str]):
        for i, row in enumerate(placements):
            queen = row.index('Q')
            if queen == col or abs(queen - col) == rowToPlace - i:
                return False
        return True

由于某种原因，这会输出[[],[]]。如果您打印结果，您可以看到结果在某个时间点上实际上是正确的，但我相信所发生的事情是将placements附加到结果中，然后这一行placements.pop(-1)正在修改位置，从而影响结果。我怎么才能防止这件事？我试着做placements = placements[:-1]，但那只是打破了它。

Answer 1

我相信正在发生的事情是，它将placements附加到results，然后这一行placements.pop(-1)正在修改placements，从而影响了结果。

这确实是原因所在。在整个过程中，placements引用一个单一的列表。从来没有为它创建新的list实例，因此每次执行result.append(placements)时，result都会收到对同一个列表的引用。

一种解决方案是获取placements的副本并将副本附加到results中。这样，您就可以确定所附加的内容之后不会改变：

result.append(placements[:])