I'm currently working on the N Queens problem, and I've got a solution that's very close, but not returning anything for some reason:

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

For some reason, this outputs [[],[]]. If you print the result, you can see the result is actually correct at some point in time, but I believe what's happening is that it's appending placements to results and then this line placements.pop(-1) is modifying placements, thus affecting the result. How do I prevent this? I tried doing placements = placements[:-1] instead, but that just broke it.

CodePudding user response：

I believe what's happening is that it's appending placements to results and then this line placements.pop(-1) is modifying placements, thus affecting the result.

That's indeed the reason. During the whole process, placements refers to one single list. Never is there a new list instance created for it, so every time result.append(placements) is executed, result receives a reference to the same list.

A solution is to take a copy of placements and append the copy to results. That way you're sure that what is appended never changes afterwards:

result.append(placements[:])