Euler's 36 Officers

In 1782 the Swiss mathematician Leonhard Euler posed a deceptively simple puzzle. Imagine you have 36 officers — six from each of six different regiments, and each regiment has one officer of each of six ranks (think: private, corporal, sergeant, lieutenant, captain, colonel). Can you arrange them in a 6×6 square so that no rank and no regiment appears twice in any row or column?

Euler could not find such an arrangement. He conjectured that it was impossible for orders of the form $n = 4k + 2$ — that is, for $n = 2, 6, 10, 14, \ldots$ — and for all other $n$ a solution exists. Half of that conjecture turned out to be correct, but the other half spectacularly wrong.

The puzzle sat open for over a century. In 1901 the French amateur mathematician Gaston Tarry settled the $n = 6$ case by exhaustive enumeration: he systematically checked every possible arrangement and showed no valid 6×6 grid exists. This is known as the thirty-six officers problem, and its solution relies on the concept of orthogonal Latin squares — one of the most elegant ideas in combinatorics.

Each cell of the 6×6 grid holds an officer described by two attributes: their rank (A–F, shown as a letter) and their regiment (1–6, shown as a number). Click a cell to cycle through the 36 possible officer types. The goal: every row and column must contain each rank exactly once and each regiment exactly once.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div id="legend" class="legend">
  <span class="leg-label">{{lbl_rank}}</span>
  <span class="leg-item rank-A">A</span><span class="leg-item rank-B">B</span><span class="leg-item rank-C">C</span><span class="leg-item rank-D">D</span><span class="leg-item rank-E">E</span><span class="leg-item rank-F">F</span>
  <span class="leg-sep"></span>
  <span class="leg-label">{{lbl_regiment}}</span>
  <span class="leg-item reg-1">1</span><span class="leg-item reg-2">2</span><span class="leg-item reg-3">3</span><span class="leg-item reg-4">4</span><span class="leg-item reg-5">5</span><span class="leg-item reg-6">6</span>
</div>
<div id="board" class="board" aria-label="{{board_aria}}"></div>
<div id="status" class="status" aria-live="polite">{{status_empty}}</div>
<div class="btns">
  <button id="btn-check" type="button">{{btn_check}}</button>
  <button id="btn-hint" type="button">{{btn_hint}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .87rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.legend { display: flex; align-items: center; flex-wrap: wrap; gap: .3rem; margin-bottom: .5rem; font-size: .8rem; }
.leg-label { font-weight: 700; color: #555; margin-right: .1rem; }
.leg-sep { width: .7rem; }
.leg-item { display:inline-flex; align-items:center; justify-content:center; width:22px; height:22px;
            border-radius:4px; font-weight:700; font-size:.78rem; border:1px solid #ccc; }
.board { display: grid; grid-template-columns: repeat(6, 46px); gap: 3px; margin: .3rem 0; }
.cell { width: 46px; height: 46px; display: flex; align-items: center; justify-content: center;
        font: 700 14px ui-monospace, monospace; border-radius: 7px; cursor: pointer;
        user-select: none; border: 2px solid transparent; transition: background .15s, border-color .15s; }
.cell.empty { background: #d2d6db; border-color: #b8bcc2; color: #888; }
.cell.empty::after { content: "·"; font-size: 1.3rem; }
.cell.filled { background: #e8eef3; border-color: #b0c4d8; color: #1d3557; }
.cell.conflict { background: #ffe0e0; border-color: #e63946; color: #c92f3c; }
.cell:hover { filter: brightness(.93); }
/* {{c_rank_colors}} */
.rank-A, .cell[data-rank="A"] { background-color: #dce8f5; }
.rank-B, .cell[data-rank="B"] { background-color: #dcf5e4; }
.rank-C, .cell[data-rank="C"] { background-color: #f5f0dc; }
.rank-D, .cell[data-rank="D"] { background-color: #f5dcf0; }
.rank-E, .cell[data-rank="E"] { background-color: #dce8f5; filter: hue-rotate(40deg); }
.rank-F, .cell[data-rank="F"] { background-color: #f5e4dc; }
.cell.conflict { background: #ffe0e0 !important; border-color: #e63946 !important; }
.status { font-size: .95rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice how a conflict appears the moment you try to fill the last rows. In every other order — $3 \times 3$, $4 \times 4$, $5 \times 5$ — a perfect arrangement exists. The $6 \times 6$ case is uniquely defiant. Euler sensed this but could not prove it; it took Tarry 119 years later to check all $9 \times 10^{21}$ essentially different grids and confirm: no solution exists.

The puzzle is really about orthogonal Latin squares. A Latin square of order $n$ is an $n \times n$ grid where each symbol from a set of $n$ symbols appears exactly once per row and once per column. Two Latin squares are orthogonal if, when you superimpose them, every ordered pair of symbols appears exactly once across the $n^2$ cells.

Euler's officers need two mutually orthogonal Latin squares of order 6: one for rank, one for regiment.

• For every prime $p$ and prime power $p^k$, orthogonal Latin squares exist. They can be built from the arithmetic of finite fields (also called Galois fields). Orders $2, 3, 4, 5, 7, 8, 9, \ldots$ all work.
• Order 2 and order 6 are the only known exceptions for small $n$. Tarry's 1901 exhaustive search confirmed order 6.
• Euler's conjecture was half-wrong. He thought all $n = 4k + 2$ orders would fail. In 1960 Bose, Shrikhande, and Parker stunned the mathematical world by constructing orthogonal Latin squares of orders 10, 14, and all other $n = 4k + 2$ with $n \geq 10$. Only $n = 2$ and $n = 6$ genuinely fail.
• Why does order 6 fail? No finite field of order 6 exists (6 is not a prime power), and the clever algebraic constructions that work elsewhere simply break down. The proof today is still essentially Tarry's: exhaustive case analysis, though modern computer searches confirm it in seconds.

The connection to graph coloring is direct: constructing a pair of orthogonal Latin squares is equivalent to edge-coloring a complete bipartite graph $K_{n,n}$ with $n$ colors. When the coloring fails, so does the square.

Orthogonal Latin squares are not a mere curiosity — they are a fundamental tool across science and engineering:

• Statistical experiment design: Ronald Fisher pioneered the use of Latin squares in agricultural trials in the 1920s. A Latin square ensures that every treatment appears once in every row (say, soil strip) and every column (say, week), controlling for two confounding variables simultaneously. Pairs of orthogonal squares control for three variables at once.
• Error-correcting codes: the algebraic structure behind Latin squares also generates Reed-Solomon codes — the error-correcting codes that protect CDs, DVDs, QR codes, and deep-space transmissions. The same finite-field arithmetic Euler lacked for $n = 6$ is what makes those codes work.
• Tournament scheduling: a round-robin tournament schedule where each pair of teams meets exactly once is a Latin square. Orthogonality adds a second criterion (different venues, different referees) that squares handle naturally.
• Sudoku: a completed Sudoku grid is a special Latin square of order 9. The added box constraint makes it stricter, but the underlying structure is the same.

Euler's officers show that sometimes the most natural-looking arrangement is the one that cannot exist — and understanding why it fails opens up the entire field of combinatorial design theory. That field now underpins everything from clinical trial protocols to the satisfiability solvers used in chip design.

Euler posed a tidy parade puzzle in 1782 and sensed it was impossible, but he could not prove it. Tarry confirmed the impossibility 119 years later through sheer exhaustive case analysis. Then, in 1960, Bose, Shrikhande, and Parker showed that Euler's wider conjecture was wrong — almost every other troublesome order does admit a solution.

What remains is a beautiful singularity: the 6×6 grid is the lone non-trivial order that truly fails. There is no clever trick, no hidden symmetry to exploit. The arithmetic simply does not close up neatly when $n = 6$.

The deeper lesson is about the power of impossibility proofs. Rather than searching forever for a solution that does not exist, mathematicians proved the ceiling and moved on — and in doing so built the theory of combinatorial designs that now protects every byte of data you transmit across an unreliable channel.