Given n==4, Return [[[".","Q",".","."],[".",".",".","Q"],["Q",".",".","."],[".",".","Q","."]],[[".",".","Q","."],["Q",".",".","."],[".",".",".","Q"],[".","Q",".","."]]]
Here is my code:
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
When I check every possible time the base condition is encountered in solver function, it is solving the question correctly. However, the appended arrays in the ans variable are changing reference each time I change a. This results in ans array containing two a lists appended in their initial state of totally empty. I cannot understand why. Please help me understand.
in the line ans.append(list(a))
you are copying one list,
but you should copy 8 of them
because a looks like this
a = [
['.', '.', 'Q', ...],
[... ],
...
]
you have to copy each element of a
so
ans.append([inner.copy() for inner in a])
# I also recommend to use `.copy()` instead `list(original)` to copy