n Queen backtracking for iterating all the position

Question

I am trying to solve the n Queen problem without any 3rd party libraries. So I am using just plain python arrays and loops. Here's nQueen function

 def nQueenBackTrack(self, row, n):
        for i in range(n):
            if self.isTheQueenSafe(row , i):
                print(row,i)
                self.board[row][i] = "Q"
                self.print_the_board()
                if row == n:
                    self.print_the_board()
                else:
                    self.nQueenBackTrack(row + 1, n)

pretty straight forward. now for my isQueenSafe function I check for horizontal and diagonal attacks from other queens.

def isTheQueenSafe(self, row,col):
        for i in range(self.N):
            # check horizontal Queens
            if self.does_board_has_a_queen_at(row,i) or self.does_board_has_a_queen_at(i, col):
                return False
            # check diagonal Queens
            s = row + col
            k = row - col
            for x in range(self.N):
                for y in range(self.N):
                    if x + y == s and self.board[x][y] == "Q":
                        return False
                    if x - y == k and self.board[x][y] == "Q":
                        return False

this is the function I am having problem with. I believe I am for checking the conditions correctly. I get this as an Output of a 4 x 4 board.

['Q', '.', '.', '.'] 

['.', '.', 'Q', '.'] 

['.', '.', '.', '.'] 

['.', '.', '.', '.']

can someone please point me to the right direction

You can make your life a lot easier by representing the queens as a 1D array. Index is row, value at that index is column. This way, rows are unique by definition, columns easily checked (all values different?) and you only have to check the diagonals. — tobias_k, Feb 09 '17 at 19:20
Quick sanity check: `isTheQueenSafe` doesn't appear to ever return `True`, right? That's probably unintentional. — Daniel Wagner, Feb 09 '17 at 19:21
it does actually, I just forgot to put the return Ture statement in the post. But ya it is there. — Shadid, Feb 09 '17 at 19:35
@Shadid: If it does return somewhere you can (and probably should) edit your post so we can see when exactly. If there is more relevant code then you should also post it. Just for the sake for completeness. Otherwise you might get the wrong answer. — dingalapadum, Feb 09 '17 at 23:38

score 1 · Answer 1 · edited May 23 '17 at 10:29

You are not handling the case when you can't place the queen anywhere.

Lets think it through:

You call your function starting and you put the first queen at (0,0)
The queen is placed because you can
You are not in the final row and hence you enter the recursion to place the queen in the next row
You try to place the queen in the second row at (0,1), then at (1,1) which both are not possible.
You then try to place it at (2,1) which succeeds thus you enter the third level of the recursion
You now can't place the queen anywhere in that row.
You reach the end of the array without having placed the queen
The recursion returns to the second row
You then (probably) even try to put another queen in the second row but you can't. The end of the second row is reached and this recursive call also returns
You then (probably) even try to put another queen in the first row but again you can't. The end of the first row is reached and the first call to nQueenBackTrack returns.
The program terminates with only having two queens placed at exactly those spots where you can see in your output.

I suggest that you debug either debug your program (Python debugging tips) or you could also put some additional print statements (for instance when entering and before returning from a method call) so you can really see what is going on.

I'm assuming some stuff:

I assume that you have rotated your board when printing it because... usually x is the column and y is the row. x goes in the horizontal direction and y in the vertical.
I also assume that you actually implemented your isTheQueenSafe-method correctly. You mention in the comments that you actually return true at some point.
I assume you don't have more code in your nQueenBackTrack method.

score 1 · Accepted Answer · answered Feb 10 '17 at 00:31

A backtracking algorithm needs to be able to undo the changes it makes to the game state. In your code's case, it should remove the queen it places when it finds a valid spot:

def nQueenBackTrack(self, row, n):
    for i in range(n):
        if self.isTheQueenSafe(row , i):
            self.board[row][i] = "Q"  # this will need to be reversed later
            if row == n:
                self.print_the_board()
            else:
                self.nQueenBackTrack(row + 1, n)
            self.board[row][i] = "."  # backtrack: reset the modified square

This code should print out all solutions, but it will leave the board empty at the end. If you only want to print the first solution you can find (and leave the board with the queens on it), you need to change the function to return a value indicating if a solution was found or not. The recursive code can then either pass on the report of success, or backtrack if the recursion was a failure:

def nQueenBackTrack(self, row, n):
    for i in range(n):
        if self.isTheQueenSafe(row , i):
            self.board[row][i] = "Q"
            if row == n:
                self.print_the_board()
                return True               # success!
            result = self.nQueenBackTrack(row + 1, n)
            if result:
                return True               # pass on report of success
            self.board[row][i] = "."      # otherwise, backtrack
    return False                          # if no solution was found, report failure

Excellent. Thank you very much for the clear explanation. I have a better understanding of permutation now. Very helpful thanks. — Shadid, Feb 10 '17 at 03:09

n Queen backtracking for iterating all the position

2 Answers2