The eight queens puzzle: a short history
Put eight queens on a chessboard so that no queen can capture another. The rule fits in one sentence, you can try it with coins on a kitchen table, and yet the puzzle has kept mathematicians and programmers busy for more than 175 years. It is also the direct ancestor of Crowns and the other region puzzles that ask for one crown per row, column and color. Here is where it came from, what it taught computer science, and what changed when regions arrived.
A question in a chess magazine
In 1848 a German chess composer, Max Bezzel, signing himself "Schachfreund" (chess friend), put the problem to readers of the Berlin chess magazine Schachzeitung. He asked how many ways there are to place eight queens on the board so that none attacks another.
A queen moves any distance along a row, a column or a diagonal. So a solution needs one queen in every row, one in every column, and never two on the same diagonal. Finding one arrangement takes patience. Finding all of them, and being sure none is missing, is the hard part.
The full count came two years later. In 1850 Franz Nauck published 92 solutions in the Leipzig Illustrirte Zeitung. His list was complete, but nobody had yet proved that it was.
Gauss and a lasting mix-up
Carl Friedrich Gauss took an interest the same year and discussed the puzzle in letters to his friend, the astronomer Heinrich Schumacher. He wrote that Nauck's 92 could be confirmed by trial and error in a few hours, a process he called Tatonniren, from the French tâtonner: to feel your way forward. The strategy he described, filling the board one row at a time, is the same one programmers learn today.
Because a famous name became attached to it, the puzzle is often wrongly credited to Gauss. The question was Bezzel's and the first full answer was Nauck's. The proof that 92 is the whole list came in 1874 from the mathematician James Whitbread Lee Glaisher. In the same year a paper by Pauls in the Deutsche Schachzeitung showed that every square board from 4 by 4 upward has at least one solution.
92 answers, or really 12
Many of the 92 solutions are the same pattern seen from another side. Turn the board a quarter turn, or hold it up to a mirror, and a solution stays a solution. Group the 92 that way and only 12 different patterns remain. Eleven of them come in eight versions each. The twelfth looks the same after a half turn, so it has only four versions: 11 × 8 + 4 = 92.
Change the size of the board and the count jumps around. Boards of 2 by 2 and 3 by 3 have no solution at all, and the 6 by 6 board has fewer solutions than the 5 by 5:
| Board | Solutions | Different patterns |
|---|---|---|
| 4 by 4 | 2 | 1 |
| 5 by 5 | 10 | 2 |
| 6 by 6 | 4 | 1 |
| 7 by 7 | 40 | 6 |
| 8 by 8 | 92 | 12 |
| 9 by 9 | 352 | 46 |
| 10 by 10 | 724 | 92 |
The largest board counted exactly is 27 by 27. A team at the Dresden University of Technology finished it in 2016, after more than a year of computing, and found 234,907,967,154,122,528 solutions. In 2021 Michael Simkin, a postdoctoral fellow at Harvard, showed that on large boards the number of solutions grows roughly like 0.143n raised to the power n.
The puzzle that taught backtracking
The general version, n queens on an n by n board, was in print by 1869. Its second life began a century later, when it became a favourite first example for programmers. In 1971 Niklaus Wirth built a solver for it, one careful step at a time, in his paper "Program Development by Stepwise Refinement". The same year Edsger Dijkstra gave it a chapter of his lecture notes, A Short Introduction to the Art of Programming, ending with a program that, as he put it, "generates 92 configurations". He also named the method plainly:
The final algorithm embodies a very general technique, so general that it has a well-established name: it is called "backtracking".
Edsger W. Dijkstra, 1971
Backtracking works the way Gauss described. Put a queen on the first safe square of row 1, then row 2, and carry on. When a row has no safe square left, step back to the previous row, move that queen to its next safe square and try again. The search never finishes a hopeless board: as soon as a partial board has no way forward, that whole branch is dropped. The same idea sits inside many puzzle solvers today, including the ones that check our Crowns boards.
The puzzle also hides a harder cousin. If some queens are already on the board and you must add the rest, deciding whether that can be done at all is NP-complete, as Gent, Jefferson and Nightingale showed in 2017. In plain terms, nobody knows a method that stays fast on every large board.
Regions and touching: the modern variant
In 2003 the puzzle maker Hans Eendebak created Star Battle for the World Puzzle Championship in Arnhem, in the Netherlands. It keeps the rows and columns, adds bold regions, and swaps the queen's long diagonals for a simpler rule: stars may not touch, not even at a corner. Many Star Battles ask for two stars in every row, column and region. The one-star version is the rule set of LinkedIn's daily Queens game, launched in 2024, and of Crowns: an n by n board, n color regions, one crown in each row, column and region, and no two crowns touching.
The touching rule is much weaker than a queen's diagonals. On an 8 by 8 board there are 92 ways to place eight queens, but 5,242 ways to place eight crowns with one per row and column and none touching. That second count is catalogued in the Online Encyclopedia of Integer Sequences as Hertzsprung's problem. All 92 queen solutions are among the 5,242, because two touching cells always share a row, a column or a diagonal. The regions have to do the rest: a good board draws them so that 5,242 candidates shrink to exactly one.
That changes what kind of puzzle it is. Bezzel asked for every answer. A region puzzle has one answer and asks you to reason your way to it. Our generator places crowns that follow the rules, grows color regions around them, and then two solvers check the result: one proves there is exactly one solution, the other must finish the board with human techniques alone. You can read those techniques in our queens puzzle techniques guide, and why the one-answer promise matters in why good logic puzzles have exactly one solution.
Try the original
The classic puzzle is still worth an evening. Take a real chessboard, work row by row as Gauss suggested, and you will find a solution long before you find all 92. Then open Crowns and notice how different it feels: no search, just one deduction after another, from 5 by 5 boards in the first levels to 10 by 10 at the end.