Euler’s 36 Officers Puzzle: The Century-Long Hunt for a Solution That Doesn’t Exist
A Puzzle With No Winning Arrangement
Euler’s 36 Officers Puzzle asks whether 36 officers—representing six military ranks across six regiments—can stand in a 6-by-6 formation so that every row and column contains each rank and each regiment exactly once. The surprising answer is no. After more than a century of searching, mathematicians proved that the requested arrangement cannot exist.
This makes the puzzle unusual. Most puzzles challenge you to discover a hidden solution; Euler’s challenge invites you to search for something mathematics has forbidden. Its story stretches from an 18th-century conjecture to an enormous hand-checked proof—and eventually to a dramatic correction of Euler’s broader prediction.
The Parade-Ground Challenge
Imagine six regiments, labeled A through F. Each regiment sends six officers, one from each of six ranks:
- Colonel
- Lieutenant colonel
- Major
- Captain
- Lieutenant
- Sub-lieutenant
That produces 36 unique officers. Colonel A and Colonel B share a rank but belong to different regiments, while Colonel A and Captain A share a regiment but hold different ranks.
The challenge is to place all 36 officers into a square containing six rows and six columns. A valid arrangement must satisfy three conditions:
- Every officer appears exactly once.
- Every row and column contains one officer of each rank.
- Every row and column contains one officer from each regiment.
The rules sound reasonable. After all, each row has six spaces and there are six ranks and six regiments. Yet those perfectly balanced numbers conceal an impossible combination.
The Latin Squares Hiding Inside the Puzzle
Euler’s problem becomes easier to understand when it is divided into two grids.
In the first grid, write only each officer’s regiment. Every row and column must contain A, B, C, D, E, and F exactly once. A grid with that property is called a Latin square.
The second grid records the ranks using the numbers 1 through 6. It must also be a Latin square because every rank must appear once in every row and column.
The real challenge arrives when the two squares are placed on top of each other. Every possible regiment-and-rank pair must appear exactly once. Two Latin squares satisfying this condition are called orthogonal Latin squares.
A smaller 3-by-3 example is possible:
| A1 | B2 | C3 | |---|---|---| | B3 | C1 | A2 | | C2 | A3 | B1 |
Each row and column contains A, B, and C once, as well as 1, 2, and 3 once. All nine letter-number combinations also appear exactly once.
Euler used Latin and Greek letters to represent the two characteristics, which led to the name Graeco-Latin square. The officer puzzle is therefore equivalent to asking for a Graeco-Latin square of order 6.
For a visual introduction to the idea, the Mathematical Association of America’s guide to Euler squares shows how paired symbols form orthogonal Latin squares.
Euler Makes a Bold Prediction
Leonhard Euler studied the problem in 1779, with his work appearing in print in 1782. He was already one of history’s most productive mathematicians, contributing to subjects ranging from number theory to mechanics.
Euler could construct pairs of orthogonal Latin squares when the grid size was odd and when it was divisible by four. Order 3 worked. Order 4 worked. Order 5 worked. But order 6 stubbornly refused to cooperate.
He began to suspect a wider rule. Euler conjectured that pairs of orthogonal Latin squares were impossible whenever the order had the form:
[ 4k+2 ]
This includes 2, 6, 10, 14, 18, and so on. Such numbers were once described as “oddly even” because they are even but not divisible by four.
Euler had not proved the conjecture. He had recognized a pattern and proposed that it continued forever. The distinction is important: a mathematical conjecture may be supported by examples and brilliant reasoning, but it does not become a theorem until it is proved.
Readers interested in another famous Euler problem can explore the Königsberg Bridge Puzzle, where he also transformed an apparently simple challenge into a deep lesson about impossibility.
Gaston Tarry’s Exhaustive Attack
For more than a century, no one could produce the 6-by-6 arrangement—and no one could conclusively prove that it was impossible.
Then French mathematician Gaston Tarry tackled the problem through exhaustive enumeration. Instead of trying a few promising patterns, he systematically organized the possible Latin squares into cases and checked whether any could have an orthogonal partner.
This was around 1900, long before modern electronic computers. The calculations and classifications had to be performed by hand. Tarry’s proof, published across 1900 and 1901, established that no pair of orthogonal Latin squares of order 6 exists. The 36 officers could never be arranged under Euler’s rules.
The result confirmed Euler’s prediction for six. Roughly 120 years after Euler studied the puzzle, the search for a classical solution was finally over.
Euler Was Right—and Also Wrong
Tarry proved that the 36 Officers Puzzle was impossible, but he did not prove Euler’s entire conjecture. That distinction produced one of the story’s greatest twists.
During the late 1950s, mathematicians R. C. Bose, S. S. Shrikhande, and E. T. Parker found constructions contradicting Euler’s general prediction. Order 10, despite having the form (4k+2), does permit a pair of orthogonal Latin squares. So do 14, 18, 22, and every larger order of that form.
By 1960, the broader question had been settled: pairs of orthogonal Latin squares exist for every positive order except 2 and 6. Euler had correctly identified the exceptional six, but the pattern he proposed from it did not continue.
This is a valuable lesson about mathematical evidence. Several examples may suggest a convincing pattern, even to a genius, without proving that the pattern is universal.
Why Proving “No Solution” Is an Amazing Feat
Finding a solution is often straightforward to verify. If someone presents a completed officer grid, you can inspect its rows and columns.
Proving that no solution exists is much harder. It is not enough to say:
- “I tried many arrangements.”
- “No one has discovered one.”
- “A computer search found nothing.”
- “Euler believed it was impossible.”
A genuine proof must rule out every legal possibility, including arrangements no person would naturally think to try.
That is why Tarry’s achievement belongs among the great feats of puzzle history. Like the famous impossible challenge behind the 15-Puzzle craze, Euler’s puzzle demonstrates that persistence alone cannot defeat a structural barrier.
A similar distinction appears in the 17-clue Sudoku challenge. Finding a Sudoku with 17 clues was one accomplishment; proving that no uniquely solvable 16-clue standard Sudoku exists required a far deeper argument.
The Puzzle’s Mathematical Legacy
The 36 Officers Puzzle helped popularize the study of Latin squares, which became an important part of combinatorics—the mathematics of arrangements, patterns, and finite structures.
Latin squares and related designs have connections to experimental planning, scheduling, coding theory, statistics, and puzzle construction. Sudoku is not itself a Latin square alone because it adds 3-by-3 box restrictions, but its rows and columns follow the same basic no-repetition principle.
The puzzle has even inspired a modern quantum variation. In 2022, researchers published a “quantum solution” involving entangled quantum states. This does not place 36 ordinary officers into the classical grid that Euler requested. Instead, it changes what an “officer” can represent by using quantum information, creating a fascinating generalization of the original mathematics. Quanta Magazine’s explanation of the quantum version offers an accessible look at that development.
The Real Solution Was the Proof of Impossibility
Euler’s 36 Officers Puzzle survived for so long because its rules seemed perfectly balanced. There were six rows, six columns, six ranks, six regiments, and exactly 36 possible pairings. Nothing looked obviously wrong.
Yet order 6 contains a hidden obstruction that no rearrangement can overcome.
The puzzle’s greatest accomplishment was therefore not a spectacular completed grid. It was the discovery that the grid could never be completed at all. Euler recognized the mystery, Tarry closed the century-long search, and later mathematicians revealed that six was not merely part of a broad pattern—it was one of only two exceptional cases.
Sometimes the most remarkable solution to a puzzle is a proof that the solution does not exist.
