Euler’s Officers

In $1782$ Leonhard Euler asked whether thirty-six officers, one of each combination of six ranks and six regiments, could be paraded in a six-by-six square so that every row and every column contained one officer of each rank and one of each regiment. He could not find an arrangement, and he conjectured that none exists. He was right about the thirty-six officers, though for a reason subtler than he could prove, and wrong about the wider claim he built on top of it. The same question with sixteen court cards, the ace, king, queen, and jack of each of the four suits, does have an answer, and a pretty one. Both are instances of a single object, the Graeco-Latin square, and the integer program that builds one is two Latin squares laid on the same grid. The construction is the subject of Chlond’s note in the INFORMS Transactions on Education puzzle column.

Two squares in one

A Latin square of order $n$ is an $n \times n$ grid filled with $n$ symbols so that each symbol appears once in every row and once in every column. A Graeco-Latin square superimposes two of them. Each cell carries an ordered pair, a rank and a suit, say; the ranks form one Latin square, the suits form another, and the two are orthogonal, meaning every one of the $n^2$ possible rank-suit pairs occurs in exactly one cell. The card version, the sixteen-officers puzzle of Chlond’s note, asks for the sixteen court cards to be set in a four-by-four array so that no row or column repeats a rank or a suit, an orthogonal pair of order-four Latin squares, and adds a flourish: each of the two main diagonals must also carry every rank and every suit.

The programming model

Variables

For each cell $(i, j)$ introduce two integer variables, $$a_{ij} \in \{0, \ldots, n - 1\}, \qquad b_{ij} \in \{0, \ldots, n - 1\},$$ the rank and the suit placed in that cell.

Constraints

Each of the two squares is Latin: every row and every column of $a$, and of $b$, holds all $n$ symbols once, which is an all-different condition on each line. Orthogonality is the one extra requirement that makes the pair Graeco-Latin: the $n^2$ ordered pairs $(a_{ij}, b_{ij})$ must all be distinct. Encoding a pair by the single number $n\, a_{ij} + b_{ij}$, this too is one all-different constraint, now over all $n^2$ cells: $$\begin{align} \operatorname{AllDifferent}\bigl(a_{i,\cdot}\bigr), \; \operatorname{AllDifferent}\bigl(a_{\cdot,j}\bigr), && \operatorname{AllDifferent}\bigl(b_{i,\cdot}\bigr), \; \operatorname{AllDifferent}\bigl(b_{\cdot,j}\bigr), \\ \operatorname{AllDifferent}\bigl(\,n\, a_{ij} + b_{ij} : 1 \le i, j \le n\,\bigr). && \end{align}$$ The sixteen-officers puzzle adds the diagonal flourish, the same all-different condition on each main diagonal of $a$ and of $b$: $$\operatorname{AllDifferent}\bigl(a_{ii}\bigr), \; \operatorname{AllDifferent}\bigl(b_{ii}\bigr), \; \operatorname{AllDifferent}\bigl(a_{i,\,n+1-i}\bigr), \; \operatorname{AllDifferent}\bigl(b_{i,\,n+1-i}\bigr).$$ There is no objective; any feasible filling is a Graeco-Latin square, and the model is infeasible exactly when none exists.

The solver

from ortools.sat.python import cp_model

def graeco(n, diagonals=False):
    """Two orthogonal n x n Latin squares (rank, suit), or None. With
    diagonals=True each main diagonal also carries every symbol once."""
    m = cp_model.CpModel()
    a = [[m.NewIntVar(0, n - 1, "") for _ in range(n)] for _ in range(n)]
    b = [[m.NewIntVar(0, n - 1, "") for _ in range(n)] for _ in range(n)]
    for i in range(n):
        m.AddAllDifferent(a[i])              # rows of a Latin
        m.AddAllDifferent(b[i])              # rows of b Latin
        m.AddAllDifferent([a[k][i] for k in range(n)])   # cols of a
        m.AddAllDifferent([b[k][i] for k in range(n)])   # cols of b
    m.AddAllDifferent([n * a[i][j] + b[i][j]   # pairs distinct
                       for i in range(n) for j in range(n)])
    if diagonals:
        m.AddAllDifferent([a[i][i] for i in range(n)])
        m.AddAllDifferent([b[i][i] for i in range(n)])
        m.AddAllDifferent([a[i][n - 1 - i] for i in range(n)])
        m.AddAllDifferent([b[i][n - 1 - i] for i in range(n)])
    s = cp_model.CpSolver()
    if s.Solve(m) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        return None
    A = [[s.Value(a[i][j]) for j in range(n)] for i in range(n)]
    B = [[s.Value(b[i][j]) for j in range(n)] for i in range(n)]
    return A, B

Calling graeco(4, diagonals=True) returns an arrangement of the sixteen court cards, drawn in Figure 19.1: read the ranks alone and they form a Latin square, read the suits alone and they form another, no rank-suit pair is repeated, and each main diagonal too holds every rank and every suit. For $n = 2$ the plain model returns nothing, because no Graeco-Latin square of order two exists; the two ranks and two suits cannot be paired four distinct ways inside a $2 \times 2$ Latin structure.

The gap at six

Euler’s own case, $n = 6$, is the one the solver cannot help with. No order-six Graeco-Latin square exists, so the model is infeasible, but confirming that by search means ruling out an enormous space of fillings. Gaston Tarry certified it in $1901$ by an exhaustive hand enumeration of the order-six Latin squares, that Euler’s thirty-six officers truly cannot be paraded; Thomas Clausen is reported to have reached the same conclusion independently as early as $1842$. The model on the page is faithful to the puzzle; it is simply asking a question whose negative answer took a person, not a solver, to certify.

Euler had conjectured more than the single case. He believed no Graeco-Latin square exists for any order $n \equiv 2 \pmod 4$, that is $6, 10, 14, 18, \ldots$. The conjecture stood for nearly two centuries and then collapsed all at once. In $1959$ and $1960$ Raj Chandra Bose, Sharadchandra Shrikhande, and Ernest Parker constructed a Graeco-Latin square of order ten and then of every order $n \equiv 2 \pmod 4$ beyond six, so the press named them “Euler’s spoilers.” The final tally is clean: a Graeco-Latin square of order $n$ exists for every $n$ except $2$ and $6$.

Sources. The integer-programming construction follows Martin J. Chlond, Puzzle—Latin Square Puzzles, INFORMS Transactions on Education volume $13$, number $2$ ($2013$), pages $126$–$128$. The thirty-six officers problem is Leonhard Euler, Recherches sur une nouvelle espèce de quarrés magiques ($1782$). The impossibility of order six was proved by Gaston Tarry, Le problème des $36$ officiers ($1900$–$1901$), and is reported, via Knuth, to have been settled independently by Thomas Clausen in $1842$. Euler’s broader conjecture was disproved by R. C. Bose, S. S. Shrikhande, and E. T. Parker, whose construction of Graeco-Latin squares for all orders $n \equiv 2 \pmod 4$ greater than six appeared in $1959$–$1960$; the surviving exceptions are exactly $n = 2$ and $n = 6$.