Error in N Queens Problem using Backtracking and Recursion

I first implemented a zero matrix indicating that all the positions of the chessboard are initially available

n=int(input())
answer=[]
restrictedIndices=[[0 for i in range(n)] for j in range(n)]
dp(n,0,restrictedIndices,answer)

and then I implemented three functions to fill the restrictedIndices

def columnFill(restrictedIndices,row,column,n):
    o=column
    restrictedIndices[row][o]=1
    while o+1<n:
        o+=1
        restrictedIndices[row][o]=1
    o=column
    while o-1>=0:
        o-=1
        restrictedIndices[row][o]=1    
    o=column
    return restrictedIndices


def rowFill(restrictedIndices,row,column,n):
    o=row
    restrictedIndices[o][column]=1
    while o+1<n:
        o+=1
        restrictedIndices[o][column]=1
    o=row
    while o-1>=0:
        o-=1
        restrictedIndices[o][column]=1
    o=row    
    return restrictedIndices


def diagonalFill(restrictedIndices,row,column,n):
    o=row
    p=column
    restrictedIndices[o][column]=1
    while o+1<n and p+1<n:
        o+=1
        p+=1
        restrictedIndices[o][p]=1
    o=row
    p=column
    while o-1>=0 and p+1<n:
        o-=1
        p+=1
        restrictedIndices[o][p]=1
    o=row
    p=column
    while o+1<n and p-1>=0:
        o+=1
        p-=1
        restrictedIndices[o][p]=1
    o=row
    p=column
    while o-1>=0 and p-1>=0:
        o-=1
        p-=1
        restrictedIndices[o][p]=1    
    o=row
    p=column
    return restrictedIndices

and then the recursive function

def dp(n,row,restrictedIndices,answer):
    print(restrictedIndices)
    if row==n:
        print("yes i got a solution")
        return -1
    print(restrictedIndices)
    for i in range(n):
        if restrictedIndices[row][i]==1:
            print("rejected",(row,i))
            continue
        
        else:
            x=[i for i in restrictedIndices]
            print(row,i)
            columnFill(restrictedIndices,row,i,n)
            rowFill(restrictedIndices,row,i,n)
            diagonalFill(restrictedIndices,row,i,n)
            dp(n,row+1,restrictedIndices,answer)

I am getting wrong output and I would kindly like to know if we can solve the problem this way and if there is a better alternative. I hope I could understand how recursion and Backtracking works through the solution

Answer

This will not work, because of the following issues:

• answer is never populated: it can therefore be nothing else than its initial value, an empty list
• Although you let dp return -1 when a solution is found, this value is never checked by the caller. So the caller does not know about it and goes to the next iteration of its for loop
• When the recursive call of dp returns, the restrictedIndices list is not returned to its previous state. This means that in the next iterations of the for loop the condition [row][i]==1 will always be True — this cell was set to 1 during the first iteration. You should make sure that each iteration of the for loop starts with the exact same state of restrictedIndices.

I will not post a working solution, as this is extensively documented on the internet, and recursive solutions for Python can be found also on Stack Overflow:

• eight queens problem in Python,
• Backtracking 8 Queens Python problems
• Solving the n-queen puzzle
• 8 Queens Solution in Python
• N Queens: backtracking solution implemented by Python generator