Eight Queen Problem - Solutions and Analysis

The Eight Queen Problem is a classical constraint satisfaction problem (CSP) stated as follows:

Place eight non-attacking queens on an 8×8 chessboard, such that no two queens share the same row, column, or diagonal.

The problem belongs to the broader class of N-Queens Problems, where N queens must be placed on an N×N board under the same non-attack constraints. The 8-Queens instance is the most historically significant and the most frequently studied because it represents the smallest N for which the problem is non-trivial and has a large enough solution space to be interesting.

Formally, the Eight Queen Problem is a member of the class of exact cover problems: you must cover exactly 8 of the 64 cells on the board such that every row, every column, and every diagonal contains at most one queen. The problem is not NP-hard (it can be solved in polynomial time for any N), but it is an excellent teaching example for exact-cover and backtracking techniques that scale to NP-hard problems.

The problem was first published by chess composer Max Bezzel in 1848 and subsequently studied by mathematician Franz Nauck, who extended it to the general N-Queens case in 1850. The legendary mathematician Carl Friedrich Gauss attempted a complete solution manually and found 72 of the 92 valid arrangements, which illustrates the difficulty of exhaustive enumeration by hand. A complete rigorous enumeration was achieved by mathematicians in the 1850s.

If you want to experience the problem before studying it formally, try the interactive 8×8 board — solving it manually provides intuition that makes the mathematical analysis much more accessible.

The Eight Queen Problem can be formulated as a constraint satisfaction problem with the following components:

Variables

Let Q_i denote the column position of the queen in row i, for i ∈ {1, 2, 3, 4, 5, 6, 7, 8}. Since we require exactly one queen per row (the row constraint is built into the variable definition), we need only 8 variables rather than 64 binary variables for each cell.

Domains

Each variable Q_i has domain {1, 2, 3, 4, 5, 6, 7, 8} — the 8 possible column positions in row i.

Constraints

For all pairs (i, j) where i ≠ j:

• Column constraint: Q_i ≠ Q_j
• Diagonal constraint: |Q_i − Q_j| ≠ |i − j|

The column constraint ensures no two queens share a column. The diagonal constraint ensures no two queens share a diagonal (both main and anti-diagonal are covered by the absolute value formulation).

Constraint Graph Structure

The constraint graph has 8 nodes (one per variable) and 28 edges (one per constraint pair, since C(8,2) = 28). Every pair of variables is constrained, making this a complete constraint graph. This density is what makes pure arc consistency insufficient to solve the problem — backtracking search with constraint propagation is required.

Integer Programming Formulation

Alternatively, the problem can be formulated as a binary integer program: introduce 64 binary variables x_ij ∈ {0,1} (1 if a queen is in cell (i,j), 0 otherwise). Add constraints: sum over each row = 1, sum over each column = 1, sum over each diagonal ≤ 1. The objective function is trivially satisfied (any feasible point is a solution). Integer programming solvers can handle this formulation, though backtracking is generally faster for the queens problem specifically.

Several algorithmic approaches have been applied to the Eight Queen Problem. Each illuminates a different aspect of algorithm design:

Backtracking Search

The most natural and widely implemented approach. Place queens one row at a time. For each row, try each column in turn. If the placement creates no conflicts, recurse to the next row. If no column in the current row is valid, backtrack to the previous row and try the next column. Backtracking achieves complete enumeration of all 92 solutions and is the approach used in the interactive algorithm visualizer.

Time complexity: O(N!) in the worst case, but constraint checking prunes the tree dramatically. In practice, the 8-Queens backtracking search visits far fewer than 8! = 40,320 nodes.

Constraint Propagation (Arc Consistency)

After each queen placement, apply arc consistency to prune impossible values from the domains of unassigned variables. The most common form is AC-3 (Arc Consistency Algorithm 3). When combined with backtracking (the MAC algorithm — Maintaining Arc Consistency), this dramatically reduces the search tree size compared to simple backtracking without propagation.

Heuristic Search

Variable ordering heuristics like MRV (Minimum Remaining Values) and value ordering heuristics like LCV (Least Constraining Value) reduce backtracking further. MRV selects the unassigned variable with the fewest valid domain values, focusing search on the most constrained parts of the problem first. On the 8-Queens problem, MRV typically finds a solution with zero or near-zero backtracking.

Explicit Constructive Methods

For large N, constructive algebraic methods generate solutions directly without search. One family of constructions uses permutations based on modular arithmetic. For even N ≡ 0 (mod 6), a specific permutation formula generates a valid queen arrangement in O(N) time. These methods are studied in combinatorics rather than algorithms.

Neural Network and Evolutionary Approaches

For large N, researchers have applied neural networks (Hopfield networks), genetic algorithms, and simulated annealing. These methods find single solutions efficiently but do not enumerate all solutions. They are studied more as demonstrations of these optimization techniques than as practical Queens solvers.

The number of solutions to the N-Queens Problem grows rapidly with N. The values for small N are well-established:

Note that N=2 and N=3 have zero solutions. The progression is non-monotonic for small N (6×6 has fewer solutions than 5×5), but for N≥8 the count grows roughly super-exponentially.

The 12 "fundamental" solutions for N=8 are those that cannot be obtained from each other by rotation or reflection. The 92 total solutions consist of these 12, each appearing with multiplicity 8 (four rotations × two reflections) — except that one fundamental solution has an 8-fold symmetry group, giving: 11×8 + 1×4 = 92.

For the 8×8 case specifically, the 12 fundamental solutions are well-documented and can be viewed at the solutions page. Memorizing even 3–4 of them provides a significant advantage when solving under time pressure.

The computational complexity of the N-Queens Problem is a nuanced topic that depends on which computational question you are asking:

Existence Problem

Given N, does a valid N-Queens arrangement exist? This is trivially solvable in polynomial time (even O(1) time, since the answer is "yes" for all N ≥ 1 except N=2 and N=3). There is no interesting complexity in the existence problem.

Construction Problem

Given N, find one valid N-Queens arrangement. For the standard N-Queens problem, efficient constructive solutions exist (O(N) time for certain families of N using algebraic constructions). However, the generalized N-Queens problem — where some cells are pre-blocked and you must find an N-Queens arrangement avoiding those cells — is NP-complete (Hoffman et al., 1969).

Enumeration Problem

Count all valid N-Queens arrangements. This problem is #P-complete (falls in the same class as counting satisfying assignments of a Boolean formula). No polynomial-time algorithm for exact counting is known unless P = #P. In practice, enumeration is done by exhaustive backtracking, and known counts for N up to 27 were computed using distributed computing resources.

Practical Complexity for N=8

For the specific 8-Queens instance, the search space is tiny by modern computing standards. A naive backtracking implementation explores at most a few hundred nodes (out of a theoretical maximum of 8! = 40,320). A modern computer enumerates all 92 solutions in microseconds. The interesting complexity arises only for large N or with additional constraints.

The Eight Queen Problem has applications far beyond recreational puzzles:

Computer Science Education

The problem appears in virtually every textbook that covers backtracking algorithms, constraint satisfaction, or artificial intelligence. It is used in courses at MIT, Stanford, Carnegie Mellon, and universities worldwide as the canonical pedagogical example because it is small enough to solve by hand, large enough to require systematic search, and the solution structure is visually intuitive. The algorithm learning section covers the educational aspects in detail.

Constraint Satisfaction Research

New constraint propagation algorithms and variable/value ordering heuristics are routinely tested on the N-Queens benchmark. The problem serves as a standardized test case because its difficulty scales predictably with N and because ground truth (exact solution counts) is available for comparison. If a new CSP algorithm can outperform standard backtracking on N-Queens, it is considered a strong result.

Distributed Computing

Computing the exact solution count for large N (currently known up to N=27) requires massive parallelization. These projects have demonstrated techniques for distributing exhaustive search across thousands of processors — techniques that generalize to other counting problems in combinatorics and statistical physics.

Combinatorics and Number Theory

The algebraic structure of N-Queens solutions connects to Latin squares, permutation groups, and modular arithmetic. Researchers have studied these connections to find general formulas for constructing solutions, to characterize which values of N admit certain symmetric solutions, and to bound the growth rate of the solution count asymptotically.

Cognitive Science

The problem has been used in studies of human spatial reasoning, working memory, and problem-solving strategy. Research comparing novices and experts on the Queens Problem has yielded insights into how pattern recognition develops through practice — with direct implications for the design of educational games and puzzles.

Explore the puzzle interactively at the 8×8 board, or review all 92 solutions at the solutions page. For the academic treatment of the algorithms, see the learn section.