History of the Eight Queens Puzzle

The Eight Queens Puzzle was first published in 1848 by Max Friedrich Wilhelm Bezzel, a German chess player and composer. Bezzel posed the puzzle in the Berliner Schachzeitung (Berlin Chess Magazine), one of the leading chess publications of the era.

Bezzel was primarily a chess problem composer — a person who creates artificial chess positions as puzzles, rather than positions arising from actual games. Chess problem composition was a respected intellectual pursuit in 19th-century Germany, and the Berliner Schachzeitung was a prominent venue for such problems.

The Original Problem

Bezzel's original question was simple to state: in how many ways can eight queens be placed on a chessboard so that no queen attacks any other? He did not necessarily provide a complete solution himself — the puzzle was posed as an open challenge to the magazine's readers.

The puzzle appeared at an interesting moment in chess history. The mid-19th century was a golden age for chess in Europe. The first modern international chess tournament was held in London in 1851. Chess clubs were proliferating in major cities. Chess magazines like the Berliner Schachzeitung served a large, engaged audience of puzzle enthusiasts.

Why Queens?

The choice of queens (rather than rooks, bishops, or knights) was deliberate. The queen is the most powerful chess piece, attacking in all eight directions simultaneously. This makes the constraint "no two queens attack each other" maximally restrictive. A similar puzzle with rooks (which attack only horizontally and vertically) would have trivially simple solutions — any arrangement with one rook per row and column works, giving 8! = 40,320 solutions.

You can explore what the puzzle actually looks like by trying our interactive puzzle. To understand the solving strategies Bezzel's contemporaries would have used, see our solving guide.

Franz Nauck published the first complete set of solutions to Bezzel's puzzle in 1850, in the Illustrirte Zeitung (Illustrated Times). Nauck made two major contributions that elevated the puzzle from a chess curiosity to a genuine mathematical problem.

Finding All 92 Solutions

Nauck systematically enumerated all 92 solutions to the Eight Queens Puzzle — an impressive achievement accomplished entirely by hand. The systematic enumeration of all solutions to a combinatorial puzzle was relatively novel at the time, and Nauck's thoroughness established a high standard for subsequent mathematical work on the problem.

Nauck's solutions confirmed that the puzzle had exactly 92 valid arrangements — not more, not fewer. This number has been verified repeatedly since then, most recently by exhaustive computer enumeration. All 92 solutions can be found on our complete solutions page.

Generalizing to N Queens

Nauck's more lasting contribution may have been his generalization of the puzzle. Rather than restricting himself to an 8×8 board, Nauck asked: how many ways can N queens be placed on an N×N board with no two attacking? This generalization — now called the N-Queens Problem — became a major topic in combinatorial mathematics and later computer science.

The N-Queens Problem is far harder than the original 8-Queens case. For large N, the exact solution count is unknown except by computer calculation. As of 2023, the exact solution count has been determined up to N = 27 (announced in 2021). See Queens Puzzle Mathematics for the solution counts by board size.

Nauck's Communication with Gauss

Nauck reportedly brought the puzzle to the attention of Carl Friedrich Gauss, which led to one of the most famous episodes in the puzzle's history. See the next section for details.

Carl Friedrich Gauss (1777–1855), one of the greatest mathematicians in history, became aware of the Eight Queens Puzzle around 1850. Gauss is known for his contributions to number theory, algebra, statistics, and physics, among many other areas. His engagement with the Eight Queens Puzzle is a fascinating footnote to his career.

Gauss's Incomplete Count

In a letter to his friend and fellow astronomer Heinrich Wilhelm Olbers in 1850, Gauss reported that he had found 76 solutions to the Eight Queens Puzzle. In a subsequent letter, he revised this to 72. Gauss clearly did not find all 92 solutions, despite his extraordinary mathematical abilities.

This is often cited as evidence that the puzzle is genuinely difficult — even the "Prince of Mathematics" missed 20 solutions. However, it is worth noting that Gauss may not have applied himself seriously to exhaustive enumeration. His letters suggest he found the puzzle entertaining but did not regard it as a deep mathematical problem.

What Gauss Missed

Gauss found 72 solutions, while the correct answer is 92 — a shortfall of 20 solutions. Historians have speculated that Gauss may have systematically excluded certain symmetrically-related solutions or made errors in checking diagonal conflicts (the hardest condition to verify by hand). No detailed record of Gauss's working method survives.

Gauss's Broader Perspective

Gauss was interested in the problem not just as a puzzle but as a mathematical phenomenon. He recognized that the puzzle belonged to a class of combinatorial problems related to permutations and Latin squares — mathematical objects he had studied in other contexts. However, he did not publish any mathematical analysis of the puzzle and it remained primarily a recreational problem during his lifetime.

The episode illustrates an important point about mathematics: even exceptional ability does not guarantee correct answers to combinatorial enumeration problems. Such problems require systematic patience as much as brilliance — which is exactly what makes them valuable for teaching algorithmic thinking.

Following Bezzel's original puzzle and Nauck's solutions, the Eight Queens Puzzle and its generalization attracted sustained mathematical attention throughout the late 19th and early 20th centuries.

Connection to Permutations

Mathematicians quickly recognized that the N-Queens Problem could be reformulated as a problem about permutations. Since each row must contain exactly one queen and each column must contain exactly one queen, every valid solution corresponds to a permutation of {1, 2, ..., N} — a bijection from rows to columns. The additional diagonal constraints then filter permutations to valid solutions.

This connection placed the N-Queens Problem within the rich theory of permutations and symmetric groups, connecting it to algebraic structures that mathematicians were actively developing in the 19th century.

Group Theory and Symmetry

As group theory developed in the late 19th century through the work of mathematicians like Cayley, Galois, and Sylow, the symmetry structure of the Eight Queens Puzzle became better understood. The 8 symmetry operations of the chessboard form the dihedral group D4 — the group of symmetries of a square — and the relationship between 12 fundamental solutions and 92 total solutions was explained precisely using this group structure.

N-Queens Solution Counts

Throughout the late 19th and early 20th centuries, mathematicians progressively computed solution counts for larger boards. Progress was slow — without computers, even computing the solution count for N = 12 or N = 13 required painstaking manual work. By the mid-20th century, the solution count was known up to about N = 15.

Latin Squares and Graph Theory

The Eight Queens Puzzle has connections to Latin squares (N×N arrays where each symbol appears exactly once in each row and column) and to graph coloring (a fundamental topic in graph theory). These connections enriched both the puzzle's mathematical context and motivated study from multiple directions within mathematics.

The most famous episode in the computer science history of the Eight Queens Puzzle came in 1972, when Dutch computer scientist Edsger W. Dijkstra used it as the central example in a landmark paper on structured programming.

Who Was Dijkstra?

Edsger Dijkstra (1930–2002) was one of the most influential computer scientists of the 20th century. He is best known for Dijkstra's algorithm (the shortest path algorithm used in GPS and network routing), his work on the semaphore synchronization mechanism, and his advocacy for formal program verification. He received the Turing Award — the highest honor in computer science — in 1972, the same year he published his famous paper on the Eight Queens Puzzle.

Structured Programming Example

In his paper "Structured Programming," Dijkstra used the Eight Queens Puzzle to demonstrate how a complex program can be developed systematically using structured control flow (loops, conditions, procedures) rather than the unstructured "goto" statements common at the time.

Dijkstra's program used the backtracking algorithm: place queens row by row, using constraint checking to detect dead ends and backing up systematically when stuck. His implementation was elegant and efficient, and it served as a model for how programming problems should be approached — with clear logical structure and provable correctness.

Why This Mattered

Dijkstra's paper arrived at a pivotal moment. The early 1970s saw the "software crisis" — programs were becoming too complex to build reliably using ad hoc methods. Structured programming, which Dijkstra championed alongside others like Niklaus Wirth and C.A.R. Hoare, provided a principled approach to writing correct programs.

By choosing the Eight Queens Puzzle as his example, Dijkstra showed that even a seemingly complex problem becomes tractable when approached with clear thinking and systematic structure. The backtracking algorithm he demonstrated became a canonical example of recursion and constraint satisfaction — techniques central to computer science and artificial intelligence.

Today, the Eight Queens Puzzle is used in introductory computer science courses worldwide precisely because Dijkstra established it as the ideal vehicle for teaching backtracking, recursion, and constraint propagation. See our algorithms guide for modern implementations.

Following Dijkstra's paper, the Eight Queens Puzzle rapidly became a standard topic in computer science education. By the 1980s, it appeared in major algorithms textbooks and programming courses around the world.

Standard Curriculum Presence

The Eight Queens Puzzle (or its generalization, the N-Queens Problem) now appears in virtually every undergraduate computer science curriculum that covers:

• Algorithms courses: As the canonical example of backtracking and depth-first search
• Artificial intelligence courses: As an example of constraint satisfaction problems (CSP)
• Programming courses: As a recursion exercise suitable for beginning programmers
• Data structures courses: As an example of tree traversal and pruning

Why It Works as a Teaching Tool

The Eight Queens Puzzle is an ideal pedagogical example for several reasons:

1. Easy to explain: Anyone who knows chess can understand the problem statement in 30 seconds
2. Non-trivial solution: The puzzle is hard enough to require systematic thinking, not just trial and error
3. Scalable: The N-Queens generalization allows exploration of exponential growth and algorithmic efficiency
4. Multiple approaches: It can be solved with pure backtracking, constraint propagation, dynamic programming, or heuristic search — illustrating a spectrum of techniques
5. Visual: The chessboard provides a natural visual representation of the problem state

Famous Implementations

Over the decades, the Eight Queens Puzzle has been implemented in virtually every programming language ever created. Famous code examples include:

• Niklaus Wirth's implementation in Pascal in his 1976 textbook "Algorithms + Data Structures = Programs"
• Knuth's treatment in "The Art of Computer Programming"
• Uses in comparing AI search strategies in Russell & Norvig's "Artificial Intelligence: A Modern Approach"

Our code implementations page shows modern implementations in Python, JavaScript, and other languages.

The Eight Queens Puzzle and its N-Queens generalization continue to generate active research and surprising connections to modern computer science and mathematics.

The 27-Queens Breakthrough (2021)

In 2021, computer scientists at the University of Sydney announced that they had computed the exact number of solutions to the 27-Queens Problem — the first time the solution count for N = 27 had been determined. The answer: 234,907,967,154,122,528 (approximately 2.35 × 10^17 solutions).

This computation took several months on a cluster of computers and required innovative algorithmic techniques to handle the combinatorial explosion. The result was reported to the On-Line Encyclopedia of Integer Sequences (OEIS), which catalogues sequence A000170 — the N-Queens solution count sequence. See Queens Puzzle Mathematics for solution counts by board size.

Machine Learning Connections

In recent years, the N-Queens Problem has been used as a benchmark for machine learning approaches to constraint satisfaction. Neural networks and reinforcement learning algorithms have been applied to finding queens solutions, with mixed results — highlighting the challenges that deep learning faces with combinatorial optimization compared to classical backtracking.

Quantum Computing

Researchers have explored using quantum computing approaches — particularly quantum annealing and variational quantum algorithms — to solve large instances of the N-Queens Problem. While quantum approaches have not yet demonstrated a practical advantage over classical methods for this specific problem, the N-Queens Problem serves as a useful test case for quantum combinatorial optimization.

Open Problem: No Closed-Form Formula

Despite nearly 175 years of study, there is still no known closed-form mathematical formula for the number of N-Queens solutions as a function of N. Finding such a formula — or proving that none exists — remains one of the most elegant open problems in combinatorial mathematics. The solution count for N = 28 and beyond also remains unknown as of 2024.

A chronological view of the Eight Queens Puzzle's major milestones: