N-Queens

The N-Queens problem is a classic backtracking puzzle: place N chess queens on an N*N board so that no two queens can attack each other. Queens attack along rows, columns, and diagonals, so every queen must be on a unique row, column, and pair of diagonals. First proposed by chess composer Max Bezzel in 1848, the problem attracted the attention of luminaries including Carl Friedrich Gauss, who worked on enumerating all solutions for the 8-queen case. Over nearly two centuries, N-Queens has become one of the most studied problems in combinatorial optimization and remains a staple of computer science education.

Historical Context

Bezzel published the 8-Queens puzzle in a German chess newspaper, and within two years Franz Nauck published both the first complete solution set and the generalization to N queens on an N*N board. Gauss corresponded about the problem but never completed a full enumeration himself. In 1874, S. Gunther and J.W.L. Glaisher developed determinant-based approaches, foreshadowing the constraint satisfaction methods used today. The problem gained renewed importance in computer science when it became a benchmark for backtracking algorithms and, more recently, for SAT solvers and genetic algorithms.

How It Works

1. Place column by column: Try placing a queen in the first available row of the current column. Since each column must contain exactly one queen, this immediately eliminates one dimension of conflict.
2. Check constraints: Verify that the placement does not conflict with any previously placed queen on the same row, column, or diagonal. Diagonal conflicts can be detected efficiently using the property that two queens share a diagonal if and only if the absolute difference of their rows equals the absolute difference of their columns.
3. Recurse: If the placement is valid, move to the next column and repeat the process.
4. Backtrack: If no valid row exists in the current column, remove the last queen placed and try the next row in the previous column. This systematic unwinding ensures every possible configuration is explored.
5. Solution found: When all N queens are placed without conflict, a valid configuration has been recorded.

An important optimization involves representing constraints with boolean arrays or bitmasks for rows, main diagonals, and anti-diagonals. This reduces the constraint check from O(N) to O(1) per placement attempt, significantly speeding up the search.

Complexity

The branching factor decreases at each level due to constraints, so the actual runtime is much better than N! in practice. For the first column there are N choices, for the second roughly N-2, and so on. The number of solutions grows rapidly: N=10 has 724 solutions, N=12 has 14,200, and N=14 has 365,596.

Techniques and Optimizations

Beyond basic backtracking, several techniques can accelerate the search. Constraint propagation eliminates impossible values for future columns as each queen is placed. Symmetry breaking exploits the fact that solutions related by rotation or reflection are equivalent, reducing the search space by up to a factor of 8. Bitwise operations represent the attacked positions as bitmasks, allowing extremely fast constraint checks on modern processors. These optimizations allow solvers to handle boards well beyond N=20.

When to Use

The N-Queens problem is a foundational example of constraint satisfaction and backtracking. It appears in computer science education, interview questions, and as a benchmark for search algorithms. The techniques used -- constraint propagation, recursive backtracking, and pruning -- apply broadly to scheduling, resource allocation, VLSI design, and combinatorial optimization problems. Understanding N-Queens provides a gateway to harder problems such as graph coloring, Boolean satisfiability, and integer programming.