About the N-Queens Problem
The N-Queens problem asks how to place N chess queens on an N×N board so that no two queens share a row, column, or diagonal. It was first posed for the 8×8 chessboard by chess composer Max Bezzel in 1848 and has 92 distinct solutions for N=8. The problem is a classic constraint-satisfaction benchmark: backtracking with constraint propagation (forward checking) dramatically prunes the search tree by eliminating columns and diagonals as each queen is placed, reducing the naïve NN search space to a manageable size.
This visualiser lets you set the board size from 4 to 12, then step through or auto-play the backtracking algorithm. Conflict cells are highlighted in red when a queen is placed; backtracking moves are shown in orange, and valid placements in green. A counter tracks how many solutions have been found and how many nodes of the search tree were visited.
Frequently Asked Questions
How many solutions exist for the N-Queens problem on an 8×8 board?
There are exactly 92 distinct solutions for N=8. Considering only fundamentally different arrangements (removing rotations and reflections of the board), there are 12 unique solutions. For N=1 there is trivially 1 solution; N=2 and N=3 have 0 solutions; the counts grow rapidly: N=12 has 14,200 solutions and N=15 has 2,279,184.
How does backtracking with constraint propagation solve N-Queens efficiently?
The algorithm places queens one per row. Before placing a queen in a column, it checks whether that column or either diagonal is already attacked. If so, it skips that column. When no valid column exists in a row, it backtracks to the previous row and tries the next column there. This column-and-diagonal filtering prunes invalid branches before they are fully explored, reducing work from O(N!) to much less in practice.
Is the N-Queens problem NP-complete?
Deciding whether a partial placement of queens can be extended to a full solution (the "N-Queens Completion" problem) was shown to be NP-complete by Gent, Jefferson, and Nightingale in 2017. However, finding one solution to the standard N-Queens problem (all N queens placed from scratch) can be done in O(N) time using closed-form constructions, so the completion variant is strictly harder than the standard problem.
What is the O(N) explicit construction for N-Queens?
Several O(N) explicit constructions exist. One due to explicit formula: if N mod 6 ≠ 2 and N mod 6 ≠ 3, place queens at columns 2, 4, 6, …, N, 1, 3, 5, …, N−1 (even columns first, then odd). Special orderings handle the N mod 6 = 2 and mod 6 = 3 cases. These constructions produce one valid solution without any backtracking, which is useful when only one solution is needed rather than all 92 (or however many).
How does symmetry reduction speed up the search?
A naive backtracking search finds all 92 solutions for N=8. By exploiting the 8-fold symmetry group of the square (4 rotations × 2 reflections), one only needs to search the first half of the first row (columns 1–4), then reflect each solution found, reducing the search by a factor of roughly 8. This symmetry-breaking is standard in combinatorial search and constraint programming.
What is forward checking in the context of N-Queens?
Forward checking is a look-ahead technique: after placing a queen, the algorithm immediately removes all attacked cells from the domains (available columns) of future rows. If any future row's domain becomes empty, the current branch is pruned immediately rather than waiting until that row is reached. For N-Queens, this is equivalent to tracking three bit-vectors: one for attacked columns, one for attacked left diagonals, and one for attacked right diagonals.
Can bit manipulation make the N-Queens solver faster?
Yes. A classic bit-manipulation solver (Martin Richards, 1997) represents attacked columns, left diagonals, and right diagonals as single integers and uses bitwise AND, OR, and shifts to compute available positions. Each placement is a single bit cleared from the available-column mask; backtracking restores the mask. This allows modern CPUs to explore millions of positions per second and can find all 92 solutions for N=8 in microseconds.
Are there any practical applications of the N-Queens problem?
The N-Queens problem is used as a benchmark for constraint solvers and parallel search. Constraint-programming systems such as Choco, Gecode, and OR-Tools include it as a standard test case. The underlying technique — placing non-conflicting elements on a structured grid — has analogues in VLSI chip design (placing non-interfering circuit elements), scheduling (assigning non-overlapping time slots), and RNA secondary structure prediction.
How many solutions does N-Queens have for large N?
The exact number of solutions Q(N) grows roughly exponentially; the sequence is OEIS A000170. Q(20) = 39,029,188,884, and Q(27) = 234,907,967,154,122,528. For N ≥ 28 exact counts have not been published as of 2024; computing Q(28) alone would require petaflop-scale computation. Asymptotic estimates suggest Q(N) ≈ (0.143 N)N but exact asymptotics are an open research problem.
What is the connection between N-Queens and Latin squares?
A solution to the N-Queens problem where the queens also occupy distinct broken diagonals (toroidal diagonals wrapping around the board) is called a "toroidal" or "modular" N-Queens solution, and it corresponds to a transversal of a cyclic Latin square. Such solutions exist only for N not divisible by 2 or 3. This connection links combinatorics, group theory, and the design of orthogonal Latin squares used in statistical experiment design.