Eight Queens (1848) — Eight Pieces, None Attacking: The Board Gauss Also Counted

Introduction — Eight pieces that attack along every line

This is a problem that appeared in a German chess magazine in 1848. Place eight queens on an 8x8 board so that no queen stands where another can capture it. The tools are a board and pieces. The rule fits in one line.

A queen moves any distance along a row, a column or a diagonal. Each time you place one, that row, that column and two diagonals are blocked. The free squares vanish quickly. Yet a way to place all eight exists. In fact there are 92 of them.

This article follows the story from Max Bezzel in 1848, through Nauck and Gauss in 1850 and Glaisher in 1874, to Dijkstra in 1971-72. In 2024, LinkedIn's Queens shows a similar kind of constraint. I write only what could be confirmed, as a historian would.

Eight queens that do not attack one another (illustration, AI-generated)

Context — A magazine problem, letters, and a race to count

In 1848 the chess problemist Max Bezzel published the eight queens problem in a Berlin chess magazine. Bezzel composed chess problems; he was not a mathematician. A question set as a board game later became a subject for mathematics.

In 1850 Franz Nauck gave 92 solutions, without proving the list complete. He is also reported to have extended the question to n queens on an n x n board.

In the same year, 1850, Gauss also worked on it in letters to the astronomer Schumacher. He had found 72 solutions when he learned of Nauck's 92. This is the account given in a recent survey paper.

The proof that 92 is the full count is credited to J. W. L. Glaisher in 1874. That same year S. Gunther proposed a method using determinants. Accounts of the problem's history differ by author, and the survey itself says so.

A desk with letters and a board, mid-nineteenth century (illustration, AI-generated)

Mechanics — One per row shrinks the search at once

Count the placements. Choosing 8 squares out of 64 gives 4,426,165,368 ways. No one can check them all by hand.

Then notice something. Two queens in one row always attack each other, so every row holds exactly one queen. All that remains is to choose a column for each row. If columns must also differ, the count drops to 8 factorial, 40,320. Checking the diagonals leaves 92.

Group the 92 by rotation and reflection and you get 12 fundamental solutions. Eleven of them come in 8 variants each; one is symmetric and has 4. That makes 11 x 8 + 4 = 92.

Dijkstra treated the problem in chapter 9 of 'A Short Introduction to the Art of Programming' (EWD316), dated August 1971. He records each row's column in an array and tracks free columns and diagonals in boolean arrays. When a path hits a dead end, the program steps back and tries another column. This stepping back is called backtracking.

A board with attacked squares and a search tree that backs up at dead ends (illustration, AI-generated)

Legacy — From a teaching example to the study of computational hardness

According to English Wikipedia, Dijkstra used this problem in 1972 to show the power of structured programming. His co-authored book 'Structured Programming' (Dahl, Dijkstra, Hoare) is from the same year, and he received the 1972 Turing Award, cited for his advocacy of structured programming.

Research on larger boards continued. All solutions had been counted up to the 27x27 board by 2016. Yet whether a solution exists at all is easy: one does exist for every n except 2 and 3.

Things get hard when some queens are placed first. In 2017 Gent, Jefferson and Nightingale showed that completing such a partial placement is both NP-complete and #P-complete. An old game now serves as a benchmark for AI solvers.

In May 2024 LinkedIn launched Queens alongside Pinpoint and Crossclimb. You place queens by row, column and colored region. It uses the same kind of constraint as eight queens. But I could not find a source where its makers say they drew on eight queens. Read it as a game of the same type, not as a proven lineage.

A line from the board to search, colored grids and screens (illustration, AI-generated)

Sources

References used for this article (the original Bezzel publication, the Nauck and Gauss letters and Glaisher's paper were not checked directly; the history relies on the survey and encyclopedia entries below):

・Wikipedia: Eight queens puzzle

・Wikipedia (Japanese): エイト・クイーン

・The n-queens problem (arXiv:2109.08083)

・Matemateca IME-USP: 8 Queens problem

・E. W. Dijkstra: EWD316, A Short Introduction to the Art of Programming

・EWD316 chapter 9: The problem of eight queens

・Wikipedia: Edsger W. Dijkstra

・Gent, Jefferson, Nightingale: Complexity of n-Queens Completion (JAIR 59, 2017)

・Wikipedia: LinkedIn (games section)

・Aftermath: LinkedIn Games (Queens rules overview)

Closing — A list of 92 without proof, and a board 170 years on

In 1850 Nauck found 92 solutions by hand. The proof that the list was complete was still missing. It came in 1874. The answer arrived first and the reason caught up later, a common order in the history of mathematics.

The 1848 question became a model of thinking in 1971, and a yardstick of difficulty in 2017. In 2024, similar constraints sit on screens people play every day.

What this board has shown, historically, is that a one-line rule does not run dry even after 170 years. Eight pieces, one board. People still place them again, in a different order.

A single queen standing on a board at night (illustration, AI-generated)