Queens Puzzle Mathematics

The N-Queens Problem is a combinatorial problem: we want to count (or find) arrangements of N non-attacking queens on an N×N board. Understanding the scale of the search space helps explain both why the problem is hard and why mathematical structure is essential.

The Naive Upper Bound: C(N², N)

The total number of ways to place N queens on N² squares (choosing N squares from N²) is:

C(N², N) = (N²)! / (N! × (N²-N)!)

For N = 8, this equals C(64, 8) = 4,426,165,368 — over 4 billion arrangements. Of these, only 92 are valid solutions.

The Row-Column Constraint: N!

Since every valid solution must have exactly one queen per row and exactly one queen per column, we can reformulate the problem: valid solutions correspond to permutations of {1, 2, ..., N} where the i-th element gives the column of the queen in row i.

This reduces the search space from C(N², N) to at most N! (permutations). For N = 8:

8! = 40,320

So we need to search through at most 40,320 permutations (rather than 4 billion+) to find all valid solutions. The diagonal constraints further reduce this to just 92 valid permutations — a reduction factor of over 400.

Computational Complexity Classification

The N-Queens Problem in its decision form (does a solution exist for an N×N board?) is actually trivial — a solution exists for all N ≥ 4. More interesting formulations include:

• Counting problem: How many solutions exist for N×N? This is a #P problem (counting problems that are computationally hard)
• Enumeration problem: List all solutions. Also computationally intensive for large N
• Optimization variants: Placing as many non-attacking queens as possible on boards with obstacles falls in NP-complete territory

Why the Diagonal Constraint is the Hard Part

Of the three types of conflicts (row, column, diagonal), diagonal conflicts are hardest to handle algorithmically because there are 2N − 1 diagonals in each direction (forward and backward), giving 4N − 2 diagonal constraints in total. For N = 8, that is 30 diagonal constraints to track simultaneously, compared to just 8 row constraints and 8 column constraints.

For an intuitive understanding, see our solving guide, which explains diagonal detection strategies accessible to beginners.

The table below shows the number of solutions to the N-Queens Problem for boards from 1×1 to 20×20. This sequence is catalogued in the On-Line Encyclopedia of Integer Sequences as OEIS A000170.

Two counts are shown: the total number of distinct solutions Q(n), and the number of fundamentally different solutions F(n) (where solutions related by board symmetry are counted as one).

Notable observations from this table:

• No solutions exist for n=2 and n=3 — the only cases (beyond n=1) with zero solutions
• n=6 has fewer solutions than n=5 (4 vs 10), illustrating non-monotonic growth
• From n=8 onward, the count grows rapidly — roughly 6–7× per increment of n
• The fundamental count is approximately Q(n)/8 for large n (due to the 8 symmetry operations)

The sequence Q(n) for n ≥ 1 is OEIS sequence A000170. Explore variants and related sequences at the OEIS website. Also see our complete list of all 92 solutions for n=8 specifically.

How does the number of N-Queens solutions Q(N) grow as N increases? This question has been studied extensively, and while no exact formula is known, the asymptotic behavior is well-characterized.

Super-Exponential Growth

The solution count Q(N) grows faster than exponentially. Looking at the table, the ratio Q(n+1)/Q(n) itself grows with n:

• Q(9)/Q(8) = 352/92 ≈ 3.8
• Q(12)/Q(11) = 14200/2680 ≈ 5.3
• Q(15)/Q(14) = 2279184/365596 ≈ 6.2
• Q(18)/Q(17) = 666090624/95815104 ≈ 7.0
• Q(20)/Q(19) = 39029188884/4968057848 ≈ 7.9

The ratio is increasing, confirming super-exponential growth.

Known Bounds

While no exact formula exists, mathematicians have established bounds on Q(N). A lower bound result from combinatorics shows:

Q(N) ≥ (N/6)^(N/6) for sufficiently large N

Upper bounds are harder to establish tightly. The trivial upper bound is N! (all permutations), but the true count is much smaller.

The Exponential Growth Constant

Computational evidence suggests that Q(N) grows roughly as:

Q(N) ≈ c · (0.143 · N)^N

where c is some constant. This is related to the permanent of a certain 0-1 matrix, which is itself a #P-hard quantity to compute exactly.

Implications for Computing

The super-exponential growth of Q(N) means that computing exact solution counts for large N is computationally intractable. For N = 27, the solution count (≈ 2.35 × 10^17) took months to compute on a large cluster. For N = 30, the computation would take orders of magnitude longer — possibly years even on the most powerful computers available today.

The relationship between the 12 fundamental solutions and 92 total solutions for the 8-Queens case is explained rigorously by group theory — specifically, by the symmetry group of the square.

The Dihedral Group D4

The set of symmetry operations on a square forms a mathematical group called the dihedral group D4 (also written D8 in some notations, since it has 8 elements). The elements of D4 are:

1. e — identity (no operation)
2. r — rotation by 90°
3. r² — rotation by 180°
4. r³ — rotation by 270°
5. s — reflection along horizontal axis
6. sr — reflection along main diagonal
7. sr² — reflection along vertical axis
8. sr³ — reflection along anti-diagonal

Orbits and Stabilizers

Given a valid queen arrangement (solution), applying any element of D4 to the board produces another valid arrangement (since the non-attacking property is preserved under isometries). The set of all arrangements reachable from a given arrangement by D4 operations forms its orbit.

Burnside's lemma (from group theory) provides a way to count the number of distinct orbits (fundamental solutions):

Number of orbits = (1/|G|) × Σ_{g ∈ G} |Fix(g)|

where |Fix(g)| is the number of solutions fixed by symmetry operation g, and |G| = 8 for D4.

Computing the Result

For the 8-Queens case:

• Identity (e): All 92 solutions are fixed. |Fix(e)| = 92
• Rotation 180° (r²): Exactly 4 solutions are self-symmetric under 180° rotation. |Fix(r²)| = 4
• All other operations: No solution is fixed. |Fix(g)| = 0

Applying Burnside's lemma:

Fundamental solutions = (1/8) × (92 + 0 + 4 + 0 + 0 + 0 + 0 + 0) = 96/8 = 12

This confirms the 12 fundamental solutions from first principles.

Generalizing to N Queens

The same analysis applies for general N, though the number of self-symmetric solutions varies. For odd N, 180° rotation always maps rows to different rows (the center row maps to itself), which changes the symmetry analysis. For even N, the analysis proceeds similarly to the N=8 case.

See the all 92 solutions page for the concrete manifestation of this symmetry analysis.

Despite nearly 175 years of study, several fundamental questions about the N-Queens Problem remain unsolved.

Open Problem 1: No Closed-Form Formula

There is no known closed-form mathematical formula that expresses Q(N) — the number of N-Queens solutions — as a function of N. Finding such a formula, or proving that no "nice" formula exists, is one of the most prominent open problems in combinatorics.

A closed-form formula would allow computing Q(1000) or Q(1,000,000) without any exhaustive computation. No such formula is known even for approximate values.

Open Problem 2: Exact Solution Counts for Large N

As of 2024, the exact solution count Q(N) is known only for N ≤ 27. Computing Q(28) would require significantly more computational resources than Q(27). The exact boundary where computation becomes infeasible with foreseeable technology is around N = 30–35.

No mathematical shortcut for computing Q(N) for specific large values of N is known.

Open Problem 3: Growth Rate Constants

While Q(N) is known to grow super-exponentially, the precise constants in the asymptotic formula remain unknown. Specifically, finding exact values of the constants c and a in formulas like Q(N) ~ c·(aN)^N would settle important questions in enumerative combinatorics.

Open Problem 4: The Modular N-Queens Problem

A variant called the toroidal N-Queens Problem asks for non-attacking queens on a toroidal board (where the edges wrap around). This variant is known to have solutions only when N is not divisible by 2 or 3. A complete characterization of exactly which N values have toroidal solutions, and how many, involves deep questions in number theory that are not fully resolved.

Semi-Open: Polynomial Algorithm?

The N-Queens counting problem is #P-hard (at least as hard as NP-hard problems), suggesting no efficient algorithm exists. However, this has not been formally proven — it is possible (though considered very unlikely) that a polynomial-time counting algorithm exists.

The history of open problems in this area is explored further on our history page.

The N-Queens Problem is not an isolated mathematical curiosity — it connects deeply to several important areas of mathematics and computer science.

Latin Squares

A Latin square of order N is an N×N array where each of N symbols appears exactly once in each row and column. The N-Queens solutions can be embedded in Latin squares: if we create an N×N array where position (i, j) = 1 if a queen is placed at row i, column j, and 0 otherwise, the resulting array has exactly one 1 per row and column — like a "sparse" Latin square.

More precisely, the column permutation defining each queen arrangement is a row of a Latin square of permutations. Latin squares are fundamental objects in combinatorics with applications to experimental design and error-correcting codes.

Graph Coloring

The N-Queens Problem can be reformulated as a graph coloring problem. Create a graph where each square of the N×N board is a vertex, and connect two vertices with an edge if they are in the same row, column, or diagonal (i.e., queens placed there would attack each other). A valid N-Queens solution corresponds to an independent set of size N in this graph — a set of N vertices with no edges between them.

Constraint Satisfaction Problems (CSP)

The N-Queens Problem is the canonical example of a constraint satisfaction problem. In the CSP framework:

• Variables: Q1, Q2, ..., QN (one per row)
• Domains: {1, 2, ..., N} (column positions)
• Constraints: Qi ≠ Qj, |Qi − Qj| ≠ |i − j| for all i ≠ j

CSP algorithms like arc consistency, forward checking, and backtracking with constraint propagation were largely developed and tested on the N-Queens Problem. This makes the puzzle foundational for artificial intelligence research.

Permutation Groups and Symmetric Polynomials

The number of N-Queens solutions Q(N) can be expressed as the permanent of a certain 0-1 matrix (related to the attack matrix of queens). Computing matrix permanents is equivalent to counting perfect matchings in bipartite graphs — a fundamental problem in algebraic combinatorics. This connection links N-Queens to deep results in the theory of symmetric functions and representation theory.

Coding Theory

Solutions to the toroidal N-Queens Problem (where the board wraps) correspond to certain error-correcting codes. Specifically, for prime N, the set of all N-Queens solutions on a toroidal board forms a structure similar to a Reed-Solomon code. This connection has applications in communications engineering.

One of the most elegant theoretical results about the N-Queens Problem comes from modular arithmetic — the mathematics of remainders.

Explicit Construction for Prime N

When N is a prime number, there are explicit formulas for constructing valid N-Queens arrangements using modular arithmetic. For prime N, define:

Queen in row i is placed at column: (2i) mod N + 1

For example, with N = 7 (prime), this gives queens at columns: 3, 5, 7, 2, 4, 6, 1 for rows 1–7. This is indeed a valid solution for the 7-Queens Problem.

Toroidal N-Queens

A stronger result holds for the toroidal N-Queens Problem, where the board is considered to wrap around (like a torus — connecting top to bottom and left to right). For prime N, there are guaranteed solutions of the form:

Queen i at column: (k·i) mod N, for any k ≠ 0 that makes all positions distinct

The toroidal problem is strictly harder than the regular problem because queens at opposite edges also attack each other through the wrap. Valid toroidal solutions exist only when N is not divisible by 2 or 3.

Why N=8 is Not Prime

Since 8 is not a prime number (8 = 2³), the modular construction does not directly apply to the standard Eight Queens Puzzle. This partially explains why 8 is an interesting special case: it is large enough to have many solutions (92), but not a prime, so the elegant modular structure that applies to 5-queens or 7-queens problems does not apply directly.

Connection to Number Theory

The toroidal N-Queens existence question — for which N do toroidal solutions exist? — is a number theory question about divisibility. The answer (solutions exist iff N is not divisible by 2 or 3) connects the puzzle to basic properties of prime factorizations. This is the most direct link between the N-Queens Problem and classical number theory.

For a practical introduction to all aspects of this puzzle, including interactive play, visit our puzzle playground. For the history of how mathematicians discovered these connections, see Eight Queens Puzzle History.