Introduction

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+2n = 4k + 2 — that is, for n=2,6,10,14,…n = 2, 6, 10, 14, \ldots — and for all other nn 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=6n = 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.

Try to Arrange Them

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.

<!-- 6x6 officer placement grid — rank (A-F) x regiment (1-6) -->
<p class="hint">Click any cell to place an officer. Each officer is identified by their <b>rank</b> (A–F) and <b>regiment</b> (1–6). Goal: every row and every column must contain each rank exactly once AND each regiment exactly once. Conflicts light up red. Can you fill all 36 cells without a single conflict?</p>
<div id="legend" class="legend">
  <span class="leg-label">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">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="6 by 6 officer placement grid"></div>
<div id="status" class="status" aria-live="polite">Click a cell to place your first officer.</div>
<div class="btns">
  <button id="btn-check" type="button">Check grid</button>
  <button id="btn-hint" type="button">Why is it impossible?</button>
  <button id="btn-reset" type="button" class="ghost">Clear grid</button>
</div>

/* Styles for the 36-officers demo */
* { 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); }
/* Subtle background tint per rank to help visual scanning */
.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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 36 Officers demo: click to cycle through all 36 officer types; conflicts highlighted in red.
const RANKS = ['A','B','C','D','E','F'];
const REGS  = [1, 2, 3, 4, 5, 6];
const N = 6;
// 6x6 grid — null means empty, {rank, reg} means occupied
const grid = Array.from({length: N}, () => Array(N).fill(null));

// Return the set of (r,c) keys that participate in any row or column conflict.
function getConflicts() {
  const bad = new Set();
  // Check rows for duplicate rank or regiment.
  for (let r = 0; r < N; r++) {
    const rankSeen = {}, regSeen = {};
    for (let c = 0; c < N; c++) {
      const v = grid[r][c]; if (!v) continue;
      if (rankSeen[v.rank] !== undefined) { bad.add(r+','+rankSeen[v.rank]); bad.add(r+','+c); }
      else rankSeen[v.rank] = c;
      if (regSeen[v.reg] !== undefined) { bad.add(r+','+regSeen[v.reg]); bad.add(r+','+c); }
      else regSeen[v.reg] = c;
    }
  }
  // Check columns for duplicate rank or regiment.
  for (let c = 0; c < N; c++) {
    const rankSeen = {}, regSeen = {};
    for (let r = 0; r < N; r++) {
      const v = grid[r][c]; if (!v) continue;
      if (rankSeen[v.rank] !== undefined) { bad.add(rankSeen[v.rank]+','+c); bad.add(r+','+c); }
      else rankSeen[v.rank] = r;
      if (regSeen[v.reg] !== undefined) { bad.add(regSeen[v.reg]+','+c); bad.add(r+','+c); }
      else regSeen[v.reg] = r;
    }
  }
  return bad;
}

function filled() {
  return grid.every(row => row.every(v => v !== null));
}

// Cycle through all 36 officer types on each click; null means remove.
function nextOfficer(cur) {
  if (!cur) return { rank: RANKS[0], reg: REGS[0] };
  const ri = RANKS.indexOf(cur.rank);
  const gi = REGS.indexOf(cur.reg);
  const next = ri * N + gi + 1;
  if (next >= N * N) return null;
  return { rank: RANKS[Math.floor(next / N)], reg: REGS[next % N] };
}

function render() {
  const conflicts = getConflicts();
  const board = document.getElementById('board');
  board.innerHTML = '';
  for (let r = 0; r < N; r++) {
    for (let c = 0; c < N; c++) {
      const cell = document.createElement('div');
      const v = grid[r][c];
      const key = r+','+c;
      if (v) {
        cell.className = 'cell filled' + (conflicts.has(key) ? ' conflict' : '');
        cell.dataset.rank = v.rank;
        cell.textContent = v.rank + v.reg;
        cell.title = i18nFmt('Rank %rank%, Regiment %reg%', { rank: v.rank, reg: v.reg });
      } else {
        cell.className = 'cell empty';
        cell.title = 'Click to place an officer';
      }
      cell.setAttribute('aria-label', v ? i18nFmt('Row %r%, column %c%: rank %rank%, regiment %reg%', { rank: v.rank, reg: v.reg, r: r+1, c: c+1 }) : i18nFmt('Row %r%, column %c%: empty', { r: r+1, c: c+1 }));
      cell.addEventListener('click', () => { grid[r][c] = nextOfficer(v); renderAndCheck(); });
      board.appendChild(cell);
    }
  }
}

function setStatus(msg, cls) {
  const el = document.getElementById('status');
  el.textContent = msg;
  el.className = 'status ' + (cls || '');
}

function renderAndCheck() {
  render();
  const conflicts = getConflicts();
  if (conflicts.size === 0 && filled()) {
    setStatus('✓ Remarkable — a valid arrangement! (But this is a smaller version; the 6×6 with all 36 distinct officers is impossible.)', 'ok');
  } else if (conflicts.size > 0) {
    setStatus(i18nFmt('✗ %n% conflict(s) detected — two officers share a rank or regiment in the same row or column.', { n: conflicts.size }), 'bad');
  } else {
    setStatus('Grid is valid so far — keep placing officers.', 'info');
  }
}

// Check button validates the current grid state.
document.getElementById('btn-check').addEventListener('click', () => {
  const conflicts = getConflicts();
  if (!filled()) {
    setStatus('Fill all 36 cells first, then check.', 'info');
  } else if (conflicts.size === 0) {
    setStatus('✓ Remarkable — a valid arrangement! (But this is a smaller version; the 6×6 with all 36 distinct officers is impossible.)', 'ok');
  } else {
    setStatus(i18nFmt('✗ %n% conflict(s) detected — two officers share a rank or regiment in the same row or column.', { n: conflicts.size }), 'bad');
  }
});

document.getElementById('btn-hint').addEventListener('click', () => {
  // Show the impossibility message regardless of current grid state.
  setStatus('Tarry proved in 1901 (by checking every case) that no valid 6×6 arrangement of 36 distinct officers exists. There is no solution — not even close!', 'bad');
});

document.getElementById('btn-reset').addEventListener('click', () => {
  for (let r = 0; r < N; r++) for (let c = 0; c < N; c++) grid[r][c] = null;
  render();
  setStatus('Grid cleared. Start over.', '');
});

render();
setStatus('Click a cell to place your first officer.', '');
Result
Console

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

The Real Complexity

The puzzle is really about orthogonal Latin squares. A Latin square of order nn is an n×nn \times n grid where each symbol from a set of nn 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 n2n^2 cells.

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

  • For every prime pp and prime power pkp^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,…2, 3, 4, 5, 7, 8, 9, \ldots all work.
  • Order 2 and order 6 are the only known exceptions for small nn. Tarry's 1901 exhaustive search confirmed order 6.
  • Euler's conjecture was half-wrong. He thought all n=4k+2n = 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+2n = 4k + 2 with n≥10n \geq 10. Only n=2n = 2 and n=6n = 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 Kn,nK_{n,n} with nn colors. When the coloring fails, so does the square.

Where It Matters

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=6n = 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.

Conclusion

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=6n = 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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/thirty-six-officers/Content licensed under CC BY-NC 4.0.