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
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