N-Queen Problem is one of the first problems taught in the Computer Science Branch when we go through the chapter of Recursion. This problem is studied well in Maths and CS.
I coded the problem in a DEPTH-FIRST SEARCH way and was hoping to get a list of positions in which I can place N-Queens on a N - by - N chessboard
import copy
# At some point, I thought recursion limit was the problem, but I don't think so.
# import sys
# sys.setrecursionlimit(1_000_000_000)
board_shape = 9
queen_moves = list()
def check_collision(var_current, var_others):
if len(var_others) > 0:
for queens in var_others:
if var_current[0] == queens[0]:
return True
elif var_current[1] == queens[1]:
return True
elif abs(var_current[0] - queens[0]) == abs(var_current[1] -
queens[1]) :
return True
return False
def n_queen(pos_X, pos_Y, queens_t, total_queens):
if pos_X > -1 and pos_X < board_shape:
if pos_Y > -1 and pos_Y < board_shape and queens_t < board_shape:
current_queen = [pos_X, pos_Y, queens_t + 1]
copy_of_moves = copy.deepcopy(total_queens)
if check_collision(current_queen, copy_of_moves) is False:
copy_of_moves.append(current_queen)
print(copy_of_moves, "\t", len(copy_of_moves))
else:
return
if len(copy_of_moves) == board_shape :
print("There is a route")
print(copy_of_moves)
return
n_queen(pos_X=pos_X + 2, pos_Y=pos_Y + 1, queens_t=queens_t+1, total_queens=copy_of_moves)
n_queen(pos_X=pos_X + 2, pos_Y=pos_Y - 1, queens_t=queens_t+1, total_queens=copy_of_moves)
n_queen(pos_X=pos_X - 2, pos_Y=pos_Y + 1, queens_t=queens_t+1, total_queens=copy_of_moves)
n_queen(pos_X=pos_X - 2, pos_Y=pos_Y - 1, queens_t=queens_t+1, total_queens=copy_of_moves)
n_queen(pos_X=pos_X + 1, pos_Y=pos_Y + 2, queens_t=queens_t+1, total_queens=copy_of_moves)
n_queen(pos_X=pos_X + 1, pos_Y=pos_Y - 2, queens_t=queens_t+1, total_queens=copy_of_moves)
n_queen(pos_X=pos_X - 1, pos_Y=pos_Y + 2, queens_t=queens_t+1, total_queens=copy_of_moves)
n_queen(pos_X=pos_X - 1, pos_Y=pos_Y - 2, queens_t=queens_t+1, total_queens=copy_of_moves)
if __name__ == "__main__":
moves = list()
# Thought I would get at least one result if I go through all the rows or columns but no luck.
for i in range(board_shape):
n_queen(i, 0, 0, moves)
I was trying to solve the N-Queen problem using Recursion. This algorithm works fine for values of board_shape up-to 5. When I enter values above 5, it only goes up-to a depth of 5 and does nothing more.
If possible, please highlight the code which is causing the problem and also, put the corrected code.
Your code does not explore all possible positions on the chessboard. The recursive calls in the n_queen function are made with fixed increments or decrements of 1 or 2 for the pos_X and pos_Y values. This approach does not explore all possible positions on the chessboard. For example, for a chessboard of size 9, the function will never try positions like (3, 4), (4, 5), etc. Also I don't see a proper termination condition for the recursion.
Try this instead:
board_shape = 9
results = []
def is_safe(board, row, col):
# Check this row on the left side
for i in range(col):
if board[row][i] == 1:
return False
# Check upper diagonal on the left side
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
# Check lower diagonal on the left side
for i, j in zip(range(row, board_shape, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True
def solve_n_queen(board, col):
# Base case: If all queens are placed, add the solution to the results list
if col == board_shape:
result = []
for i in range(board_shape):
for j in range(board_shape):
if board[i][j] == 1:
result.append([i, j])
results.append(result)
return
# Recursive case: Try to place the queen in all rows of the current column
for i in range(board_shape):
if is_safe(board, i, col):
board[i][col] = 1
# Recur to place rest of the queens
solve_n_queen(board, col + 1)
# If placing queen in board[i][col] doesn't lead to a solution,
# remove the queen from board[i][col]
board[i][col] = 0
def n_queens():
board = [[0 for _ in range(board_shape)] for _ in range(board_shape)]
solve_n_queen(board, 0)
return results
if __name__ == "__main__":
solutions = n_queens()
for solution in solutions:
print(solution)