CODEWITHSUNDEEP
pythonrecursionbacktrackingn-queens
BigBoy1337
BigBoy1337

Reputation: 4993

Why is my N Queens algorithm reaching the last row?

I think I understand the point of the NQueens algorithm - you check each row for available spaces and if they exist, put a queen there, and recursively call the algorithm to the next row. Here is my algorithm (with N size 3)

from typing import List
import pdb
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        self.solutions = 0 
        self.attack_zone = [[0]*n for i in range(n)]
        self.size = n
        self.backtrack_nqueens(0,0) #start on row 0 
        return self.solutions
    def backtrack_nqueens(self,row,iteration):
        #starting at row
        for col in range(self.size):
            if self.is_not_under_attack(row,col):
                print("on iteration",iteration,row,col,"was a safe place for some reason")
                #adds queen to this row
                self.place_or_remove_queen(row,col,True)
                if row + 1 == self.size:
                    ## THIS SHOULD NEVER HAPPEN 
                    self.solutions += 1
                else:
                    self.backtrack_nqueens(row+1,iteration+1)
                #removes queen from this row
                self.place_or_remove_queen(row,col,False)

    def place_or_remove_queen(self,row,col,place):
        flag = 1 if place else 0 
        self.attack_zone[row] = [flag]*self.size
        #for col
        for r in range(self.size):
            self.attack_zone[r][col] = flag
        #lower right
        for r,c in zip(range(row,self.size,1),range(col,self.size,1)):
            self.attack_zone[r][c] = flag
        #upper right
        for r,c in zip(range(row,-1,-1),range(col,self.size,1)):
            self.attack_zone[r][c] = flag
        #lower left
        for r,c in zip(range(row,self.size,1),range(col,-1,-1)):
            self.attack_zone[r][c] = flag
        #upper left
        for r,c in zip(range(row,-1,-1),range(col,-1,-1)):
            self.attack_zone[r][c] = flag

    def is_not_under_attack(self,row,col):
        return self.attack_zone[row][col] == 0
s = Solution()
print(s.solveNQueens(3))

When I run this, self.solutions ends up at 3 - basically it finds 3 places for a queen which we all know shouldn't happen. I don't understand how its getting to that row where I said ##THIS SHOULD NEVER HAPPEN.

The only thing I can think of is that I am somehow removing a queen that shouldn't be removed? So my attack_zone has empty spaces when it shouldn't. Can someone point out what I am doing wrong in the recursion that would cause this and why?

Upvotes: 4

Views: 124

Answers (1)

a_guest
a_guest

Reputation: 36289

The problem is that when you remove a queen, you mark the corresponding squares as "free", i.e. setting their "threat count" to zero, regardless of whether another queen also threatens that square. Considering your example the following happens:

# Iteration 1     # Iteration 2     # Iteration 3

| 1 | 1 | Q |     | 1 | 1 | Q |     | 0 | 0 | Q |
+---+---+---+     +---+---+---+     +---+---+---+
| 0 | 1 | 1 |     | Q | 1 | 1 |     | 0 | 0 | 0 |
+---+---+---+     +---+---+---+     +---+---+---+
| 1 | 0 | 1 |     | 1 | 1 | 1 |     | 0 | 0 | 1 |

On iteration #3 the queen on (1, 0) is removed and all corresponding squares are flagged as 0, also the ones that are actually threatened by the queen on (0, 2). The same happens for queens on (1, 1) and (1, 2) and the latter eventually leads to a free square on (2, 0) which is the last row.

In order to make the algorithm work you can maintain a "threat count" which tracks by how many queens a square is threatened. Placing a queen increases that count by one and removing a queen reduces it by one. You can realize this by changing the value of flag to flag = 1 if place else -1 and then use self.attack_zone[r][c] += flag everywhere instead of self.attack_zone[r][c] = flag. This gives then the following picture:

# Iteration 1     # Iteration 2     # Iteration 3

| 1 | 1 | Q |     | 2 | 2 | Q |     | 1 | 1 | Q |
+---+---+---+     +---+---+---+     +---+---+---+
| 0 | 1 | 1 |     | Q | 2 | 2 |     | 0 | 1 | 1 |
+---+---+---+     +---+---+---+     +---+---+---+
| 1 | 0 | 1 |     | 2 | 1 | 1 |     | 1 | 0 | 1 |

Upvotes: 5

Related Questions