N-Queens Python solution generating incorrect output-CodePudding

I am trying to solve the n-queens problem. I wrote a solution for the problem as follows:

def isSafe(board,row,col):
    for i in range(row):
        if board[i][col]==1:
            return False
        
    x,y = row,col
    # print(x,y)
    while x>=0 and y>=0:
        if board[x][y]==1:
            return False
        x-=1
        y-=1

    x,y = row,col
    # print(x,y)
    while x>=0 and y<len(board):
        if board[x][y]==1:
            return False
        x-=1
        y =1

    return True
        
        

def solveNQueens(n):
    ans = []
    def placeQueens(board,row):
        if row==len(board):
            ans.append(board)
            return

        for i in range(len(board)):
            if isSafe(board,row,i):
                board[row][i]=1
                # print(board)
                placeQueens(board,row 1)
                board[row][i]=0
        return
                
        
    
    board = [[0 for i in range(n)] for j in range(n)]
    # print(board)
    
    placeQueens(board,0)
    
    print(ans) 

solveNQueens(4)

The above code uses recursive backtracking to solve the n queens problem. The placeQueens function appends the board combination directly to ans list when all the queens are assigned a row but when I try to print ans, all the places are marked as zeroes.

e.g for n=4:

Expected ans = [[[0,1,0,0],[0,0,0,1],[1,0,0,0],[0,0,1,0]],[[0,0,1,0],[1,0,0,0],[0,0,0,1],[0,1,0,0]]]

Answer printed = [[[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]]]

Where am I going wrong??

I tried appending the board positions one by one to the ans list and the code works fine.

def isSafe(board,row,col):
    for i in range(row):
        if board[i][col]==1:
            return False
        
    x,y = row,col
    # print(x,y)
    while x>=0 and y>=0:
        if board[x][y]==1:
            return False
        x-=1
        y-=1

    x,y = row,col
    # print(x,y)
    while x>=0 and y<len(board):
        if board[x][y]==1:
            return False
        x-=1
        y =1

    return True
        
        

def solveNQueens(n):
    ans = []
    def placeQueens(board,row):
        if row==len(board):
            ans.append([])
            # print(board)
            for i in range(len(board)):
                ans[-1].append([])
                for j in board[i]:
                    if j==0:
                        ans[-1][-1].append(0)
                    else:
                        ans[-1][-1].append(1)
            return

        for i in range(len(board)):
            if isSafe(board,row,i):
                board[row][i]=1
                # print(board)
                placeQueens(board,row 1)
                board[row][i]=0
        return
                
        
    
    board = [[0 for i in range(n)] for j in range(n)]
    # print(board)
    
    placeQueens(board,0)
    
    print(ans)

solveNQueens(4)

Why is the first code generating incorrect output, when both the codes are logically similar??

CodePudding user response：

So, you have, correctly, avoided the trap that arrays are "pointers" (see note at last paragraph), and therefore that using several time the same array would make all the instance alias of each other here:

board = [[0 for i in range(n)] for j in range(n)]

You were right to do so. The trap here would have been to say

board = [[0]*n]*n

Note that the inner [0]*n would not have been a problem. But the outer one, would have lead to the well known situation where changing board[1][2]=1 for example, would have changed board to [[0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 1, 0], [0, 0, 1, 0]], because all board[i] are the same array of ints.

Reason why I take time to explain you something you apparently already know, and to explain a mistake you haven't made, is that this is the same reason why your code doesn't work. Because "arrays are pointers".

So, here

        if row==len(board):
            ans.append(board)

what you append here is board. An array. So a "pointer". If board content change after that, it will impact the content of what you have added to ans. So the content of ans. Each thing you appended to ans, are just several time the same board (so, even if it were not full 0, you were doomed to have only identical boards in ans). And even more, since at the end of your code, board is full 0, well ans if several times board, that is several time full 0.

Just, replace

ans.append(board)

ans.append([[board[i][j] for j in range(n)] for i in range(n)])

(or ans.append([x.copy() for x in board]), but the double loop has the advantage to resemble what you did for initialization)

So to add to ans not board but a new array whose content is the same as board content (and that will not change when board changes), and the result is (I've just tried, with your first code, and only this change)

[[[0, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 1, 0]], [[0, 0, 1, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0]]]

That is exactly what you were expecting.

So, your code (the recursive search, and all) works exactly as intended. Your only problem was a "pointer" problem

Note: when I say "pointer" it is by analogy with some other languages were you can use "pointer" to creates some sort of alias of a variable. In reality it is not accurate to say thing like "arrays are pointers". It is not like not all data type behave the same in python from this point of view. There aren't some data-type that are aliased and other that are copied. It is just that you wouldn't have made this mistake with, for example a string, simply because string being unmutable, if board had been a string, it couldn't have changed.

I ranted a while on this matter in another post