In N Queen problem, where we need to place N queens in NxN Matrix, I need to get total number of possible matrices, and I'm storing resultant matrices in variable called 'ans'. But when I print 'ans' I'm getting wrong ans.
# To place N Queens in NxN MAtrix, Any placement of queens in its row, column or diagonal is considered invalid
def NQueens(mat, N, row, column, rightDiag, leftDiag):
#Base Case, if we reach row same as N => we have placed N queens
if row == N:
temp = tuple(mat.copy())
ans.append((temp))
# Here I'm getting correct one
print(ans)
return
#check all columns to place the queen
for c in range(len(mat)):
if ( c in column or (c+row) in rightDiag or (row-c) in leftDiag):
continue
else:
mat[row][c] = 1
column.add(c)
rightDiag.add(row+c)
leftDiag.add(row-c)
NQueens(mat, N, row+1, column, rightDiag, leftDiag)
#UnDO
mat[row][c] = 0
column.remove(c)
rightDiag.remove(c+row)
leftDiag.remove(row-c)
mat = [[0 for i in range(4)] for j in range(4)]
ans= []
N = len(mat)
column = set()
rightDiag = set()
leftDiag = set()
print(ans)
NQueens(mat, N, 0, column, rightDiag, leftDiag)
# Here I'm getting wrong ans
print(ans)
Expected is
[([0, 0, 1, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0]), ([0, 0, 1, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0])]
But I'm getting
[([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])]