Stuck in backtracking while trying to solve NQueens problem

Question

I am trying to write a code to solve N-Queen problem (its not optimized). The aim is to identify all possible scenarios, but got stuck in backtracking.

I kind of see what is the problem but not able to fix it. When I am trying to backtrack, it's not resetting the previous row.

can someone identify what am I doing wrong.

from array import *

N = 4

def prnt (board):
    for x in range(N):
        for y in range(N):
            print (board[x][y], end = " ")
        print()


def checkdiag(board, row, col):
    T = [row,col]
    for x in range(N):
        for y in range(N):
            # print("diag values", T, x, y)
            if (abs(T[0] - x) == abs(T[1] - y)):
                if board[x][y] == 1:
                    # print("diag values board", T, x, y)
                    return 1
    return 0


def checkrow(board, row, col):
    T = [row,col]
    for x in range(N):
        for y in range(N):
            # print("row values", T, x, y)
            if (T[0] == x):
                if board[x][y] == 1:
                    # print("row values board", T, x, y)
                    return 1
    return 0

def checkcol(board, row, col):
    T = [row,col]
    for x in range(N):
        for y in range(N):
            # print("col values", T, x, y)
            if (T[1] == y):
                if board[x][y] == 1:
                    # print("col values board", T, x, y)
                    return 1
    return 0


def isSafe(board, row, col):
    if (checkdiag(board, row, col) == 0 and checkcol(board, row, col) == 0 and checkrow(board, row, col) == 0):
       # print ("row, col, diag", checkrow(board, row, col), checkcol(board, row, col), checkdiag(board, row, col))
        return 0
    else:
        return 1
    

def reset (board, row, N):
    for x in range(N):
        board[row][x] = 0



def backtrack(board, row, N):
    # print("backtrack")
    # prnt(board)
    # print("row in backtrack", row)
    if row >= N:
        return 'success'
    for col in range(N):
        # print ("backtrack before", row, col)
        safe = isSafe(board, row, col)
        # print (" Safe value", safe)
        if safe == 0:
            print ("backtrack IS safe", row, col)
            prnt(board)
            board [row][col] = 1
            backtrack(board, row+1, N)
        else:
            print ("backtrack NOT safe", row, col)
            board [row][col] = 0
            prnt(board)
    #reset (board, row - 1, N)
            # row = row -1
                
if __name__ == '__main__':
    board = [ [0] * N for _ in range(N)]
    prnt(board)

    if (backtrack(board, 0, N) == 'success'):
        prnt(board)

Does this answer your question? [List changes unexpectedly after assignment. Why is this and how to prevent it?](https://stackoverflow.com/questions/2612802/list-changes-unexpectedly-after-assignment-why-is-this-and-how-to-prevent-it) — Code-Apprentice, May 07 '21 at 18:59
The above link explains why you see the changes to your board persist. To fix the problem, either make a copy of the board each time you call `backtrack()` or reassign the current cell to clear it out. — Code-Apprentice, May 07 '21 at 18:59
Also read [this article](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) for tips on debugging your code. — Code-Apprentice, May 07 '21 at 19:00

score 0 · Accepted Answer · answered May 07 '21 at 18:56

You need to reset the cells once the backtracking finishes slowing the subproblem each time so that the value is reset and other squares can be considered safe

def backtrack(board, row, N):
    # print("backtrack")
    # prnt(board)
    # print("row in backtrack", row)
    if row >= N:
        return 'success'
    for col in range(N):
        # print ("backtrack before", row, col)
        safe = isSafe(board, row, col)
        # print (" Safe value", safe)
        if safe == 0:
            print ("backtrack IS safe", row, col)
            prnt(board)
            board [row][col] = 1
            backtrack(board, row+1, N)
            # don't forget to reset this location after being done
            board [row][col] = 0
        else:
            print ("backtrack NOT safe", row, col)
            board [row][col] = 0
            prnt(board)
    #reset (board, row - 1, N)
            # row = row -1

Stuck in backtracking while trying to solve NQueens problem

1 Answers1