👀 Views: 2 💬 Answers: 1 📅 Created: 2025-06-05

algorithms backtracking n-queens Python

I tried several approaches but none seem to work. I'm working on a backtracking solution for the N-Queens question in Python, where I need to place N queens on an N x N chessboard such that no two queens threaten each other. The implementation seems to only count some of the valid configurations. My goal is to return the total number of valid arrangements. Below is my code snippet: ```python def is_safe(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, len(board)), range(col, -1, -1)): if board[i][j] == 1: return False return True def solve_n_queens_util(board, col): if col >= len(board): return 1 # Found a valid arrangement count = 0 for i in range(len(board)): if is_safe(board, i, col): board[i][col] = 1 # Place queen count += solve_n_queens_util(board, col + 1) board[i][col] = 0 # Backtrack return count def solve_n_queens(n): board = [[0 for _ in range(n)] for _ in range(n)] return solve_n_queens_util(board, 0) print(solve_n_queens(4)) # Expected output is 2 ``` When I run this with `n = 4`, I expect to see 2 as the number of solutions, but I’m getting an incorrect output. I’ve validated the base cases and backtracking logic, and I'm not seeing any syntax errors or runtime issues. I also tried adding print statements to check the board state, but the behavior still seems off. Is there a flaw in the logic for counting the solutions, or am I missing something crucial in how the board is managed? Any insights or suggestions would be greatly appreciated! My development environment is Linux. Has anyone else encountered this?