Python List gets overwritten in recursion, N Queen

37 Views Asked by At

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])]

0

There are 0 best solutions below