👀 Views: 82 💬 Answers: 1 📅 Created: 2025-06-12

algorithm backtracking N-Queens Python

I'm experimenting with I'm sure I'm missing something obvious here, but I'm working on solving the N-Queens question using recursive backtracking in Python 3.10, but I'm working with a 'Time Limit Exceeded' behavior on larger board sizes (like 15x15)... My implementation checks each row and column recursively but seems to get exploring in deeper recursion levels. Here's the code I've been using: ```python class NQueens: def __init__(self, n): self.n = n self.solutions = [] def is_safe(self, board, row, col): for i in range(col): if board[row][i] == 1: return False for i, j in zip(range(row, -1, -1), range(col, -1, -1)): if board[i][j] == 1: return False for i, j in zip(range(row, self.n), range(col, -1, -1)): if board[i][j] == 1: return False return True def solve_n_queens_util(self, board, col): if col >= self.n: self.solutions.append([''.join('Q' if c else '.' for c in row) for row in board]) return for i in range(self.n): if self.is_safe(board, i, col): board[i][col] = 1 self.solve_n_queens_util(board, col + 1) board[i][col] = 0 # backtrack def solve_n_queens(self): board = [[0]*self.n for _ in range(self.n)] self.solve_n_queens_util(board, 0) return self.solutions n_queens = NQueens(15) result = n_queens.solve_n_queens() print(f'Found {len(result)} solutions.') ``` I noticed that the algorithm works fine for smaller sizes (like 8 or 10) but struggles significantly with 15. I've also tried to optimize the `is_safe` function, but the performance is still poor. Is there a more efficient approach or optimization I can apply to handle larger board sizes effectively? Any suggestions or best practices would be greatly appreciated! For context: I'm using Python on Linux.