N-Queens-Solver

An elegant and highly optimized Python implementation to solve the classic N-Queens Problem. This script uses Depth-First Search (DFS) and Backtracking to find all possible configurations where $N$ chess queens can be placed on an $N \times N$ chessboard so that no two queens threaten each other.

🚀 Features

• Optimized State Representation: Instead of passing a heavy 2D matrix around, the algorithm uses a highly efficient 1D array to represent the board state, where the index represents the row and the value represents the column of the placed queen.
• Backtracking Algorithm: Intelligently prunes invalid branches of the search tree. The moment a queen placement becomes invalid, it abandons that path and backtracks, saving massive amounts of computational power.
• Visual Board Printer: Includes a print_visual_boards helper function that translates the numerical solutions into an intuitive, text-based grid (using Q for Queens and . for empty squares).
• Zero Dependencies: Built entirely with standard Python. No external libraries required.

🧠 How the Algorithm Works

To solve the puzzle, the algorithm places queens row by row. For each row, it tries placing a queen in every column (from $0$ to $N-1$) and runs a safety check (is_safe):

1. Column Check: It ensures no previously placed queen shares the same column.
2. Diagonal Check: It uses the mathematical property of a chessboard diagonal: the absolute difference between the rows must equal the absolute difference between the columns. If $| \text{row}_1 - \text{row}_2 | = | \text{col}_1 - \text{col}_2 |$, the queens are on the same diagonal and the position is unsafe.
3. Recursive Branching: If the position is safe, the queen is temporarily placed, and the function recursively calls itself for the next row. If it hits a dead end, it pops the last queen off the board (backtracks) and tries the next column.

🛠️ Requirements & Running

This project requires Python 3.x.

1. Clone the repository or download the n_queens.py file.
2. Open your terminal or command prompt.
3. Run the script using:

python n_queens.py

💻 Code Example & Usage

You can use the dfs_n_queens function to generate the raw coordinate arrays, or pair it with the visualizer to see the actual board layouts:

# Solve the problem for a 4x4 board
n_size = 4
results = dfs_n_queens(n_size)

# Print the solutions beautifully
print_visual_boards(results, n_size)

Expected Output Example (for a 4x4 board):

--- Solution 1 ---
.  Q  .  .
.  .  .  Q
Q  .  .  .
.  .  Q  .

--- Solution 2 ---
.  .  Q  .
Q  .  .  .
.  .  .  Q
.  Q  .  .

🤝 Contributing

Contributions are always welcome! If you want to enhance this project—such as adding a graphical interface (GUI), tracking the time complexity as $N$ grows, or finding only the unique solutions (excluding reflections and rotations)—feel free to fork the repository and open a Pull Request.