Trouble with Recursive Backtracking for N-Queens solution in Python, Endless Loop guide
I'm trying to implement a recursive backtracking algorithm to solve the N-Queens question in Python. The idea is to place N queens on an NxN chessboard such that no two queens threaten each other. However, my implementation seems to get exploring in an endless loop when trying larger board sizes like 8x8. Here’s the code I have: ```python def solve_n_queens(n): def is_safe(board, row, col): # Check this column on upper side for i in range(row): if board[i][col] == 1: return False # Check upper diagonal on left side for i, j in zip(range(row, -1, -1), range(col, -1, -1)): if board[i][j] == 1: return False # Check upper diagonal on right side for i, j in zip(range(row, -1, -1), range(col, n)): if board[i][j] == 1: return False return True def solve_util(board, row): if row >= n: return True for col in range(n): if is_safe(board, row, col): board[row][col] = 1 if solve_util(board, row + 1): return True board[row][col] = 0 # Backtrack return False board = [[0 for _ in range(n)] for _ in range(n)] if not solve_util(board): return "Solution does not exist" else: return board print(solve_n_queens(8)) ``` What’s happening is that when I run this for `n = 8`, it seems to be exploring in a loop without returning any output. I've checked the `is_safe` function and it looks correct to me, but I think the scenario might lie in the recursive calls in the `solve_util` function. I've tried adding print statements to trace which rows and columns are being checked, and I can see that it's repeatedly trying the same configurations, which leads me to think it’s not correctly backtracking, but I’m unsure where the logic breaks. Any guidance on what might be causing this endless loop would be greatly appreciated! I'm working on a web app that needs to handle this. Is there a better approach?