I've been practicing the standard recusion and backtracking examples online, and came across the N-queens problem (in the LeetCode setting). After a lot of tinkering, I managed to apply a recursion in order to retrieve ANY, not all, solutions for a given board size n.
However, my algorithm works up to n=8, printing out valid board configurations, but invalid ones when n=9 or equal to the few higher numbers I tried. Invalid meaning that some board rows are full of dots and not populated by a "Q" queen, but the backtracking fails to catch that, possibly due to a buggy recursion.
For example, for n=9, this is the output:
testing backtrack
['Q........', '..Q......', '....Q....', '.Q.......', '...Q.....', '........Q', '.........', '.........', '.........']
testing backtrack
['..Q......', 'Q........', '...Q.....', '.Q.......', '....Q....', '........Q', '.........', '.........', '.........']
testing backtrack
['.Q.......', '...Q.....', 'Q........', '..Q......', '....Q....', '........Q', '.........', '.........', '.........']
testing backtrack
['.Q.......', '...Q.....', '.....Q...', 'Q........', '..Q......', '....Q....', '......Q..', '.........', '.........']
testing backtrack
['.Q.......', '....Q....', '......Q..', '...Q.....', 'Q........', '..Q......', '.....Q...', '.........', '.........']
testing backtrack
['.Q.......', '...Q.....', '.....Q...', '.......Q.', '..Q......', 'Q........', '......Q..', '....Q....', '.........']
testing backtrack
['.Q.......', '...Q.....', '.....Q...', '..Q......', '....Q....', '.........', 'Q........', '.........', '......Q..']
testing backtrack
['.Q.......', '...Q.....', '......Q..', '..Q......', '.......Q.', '.....Q...', '.........', 'Q........', '....Q....']
testing backtrack
['.Q.......', '...Q.....', '.....Q...', '..Q......', '........Q', '.........', '....Q....', '.......Q.', 'Q........']
and you can see that in all cases, at least one row in the board seems not populated by a Queen.
Can anyone pinpoint to me where the backtracking may be failing in the algorithm below? Thank you in advance!
class Solution:
def __init__(self) -> None:
self.board = ["."*n] * n
self.n_queens = n
self.queenPos = []
def solveNQueens(self, n: int) -> list[list[str]]:
def changeLetter(letter, i,j):
# change letter in board
s = list(self.board[i])
s[j] = letter
self.board[i] = "".join(s)
if letter == "Q":
self.queenPos.append([i,j])
else:
self.queenPos.pop()
def boardOk(k,l):
# print(self.queenPos)
def check_attack(piece_1, piece_2):
# check if they are in the same row
if piece_1[0] == piece_2[0]:
return True
# check if they are in the same column
elif piece_1[1] == piece_2[1]:
return True
# check if they are in the same diagonal
elif abs(piece_1[0] - piece_2[0]) == abs(piece_1[1] - piece_2[1]):
return True
else:
# print("queens are not attacking in diagonal")
return False
if len(self.queenPos)>0:
# print(self.queenPos)
for pos in self.queenPos:
if check_attack([k,l], pos):
return False
return True
def backtrack(numQueens, i, j):
if boardOk(i,j):
changeLetter("Q", i,j)
self.n_queens-=1
else:
return
if self.n_queens<=0:
return
for k in range(n):
for l in range(n):
backtrack(self.n_queens, k, l)
i=0
while self.n_queens!=0:
print(f"\ntesting backtrack")
# print(f"\ti={i}")
self.board = ["."*n] * n
self.n_queens = n
self.queenPos = []
backtrack(n, i, 0) # this works for all cases except 9 instead of backtrack(n,0,i) which doesn't except for 4
print(self.board)
if i+1<n :
i+=1
else:
break
return
if __name__=="__main__":
n=9
sol = Solution()
sol.solveNQueens(n)
Ok, forget my comments. I thought the diagonal test was wrong, I just thought you applied a different idea wrongly, but the idea you applied was correct.
Your actual problem is that you are not backtracking correctly: You just try the first position for each Queen, and only retry placing the first one. backtrack needs to actually backtrack, e.g. erase it's changes:
def backtrack(numQueens, i, j):
if boardOk(i,j):
changeLetter("Q", i,j)
self.n_queens-=1
else:
return False # This is failing
if self.n_queens == 0:
return True # We found a solution
for k in range(n):
for l in range(n):
if backtrack(self.n_queens, k, l):
return True # We found a solution
changeLetter(".", i, j) # Remove the Queen we tried from the board.
self.n_queens += 1
return False # None of the tries for other Queens works
and the while loop inside solution can be a for loop:
self.board = ["." * n] * n # You don't need to reset these each loop. backtrack cleans up behind it.
self.n_queens = n
self.queenPos = []
for i in range(n):
if backtrack(n, i, 0):
print(self.board)
return self.board
else:
raise ValueError("We did not find a solution")