xliii. Latin Squares and Euler's 36 Officers

Problem (Euler, 1782). Six regiments each send six officers of six different ranks. Can the 36 officers stand in a $6 \times 6$ square so that every row and every column contains each regiment once and each rank once?

Answer. No. The ranks form a Latin square (each symbol once per row and column), the regiments form another, and the requirement that every (rank, regiment) pair appears exactly once says the two squares are orthogonal. Orthogonal Latin squares (Graeco-Latin squares) exist for every order except 2 and 6.

Order $n$	Mutually orthogonal Latin squares (MOLS)	Source
prime power $q$	$q - 1$ , the maximum possible	finite field: $L_{a} (x, y) = a x + y$
$n = q_{1} q_{2} \dots$ (prime powers)	at least $min (q_{i}) - 1$	MacNeish: Kronecker products
$n \neq \equiv 2 (mod 4)$	at least 2	MacNeish (every prime-power factor is $\geq 3$ )
$n = 2$	1 (no orthogonal pair)	trivial
$n = 6$	1 (no orthogonal pair)	Tarry (1900); exhaustive search below
$n \equiv 2 (mod 4)$ , $n \geq 10$	at least 2	Bose, Shrikhande and Parker (1959), disproving Euler’s conjecture
any $n$	at most $n - 1$	normalization argument

$n$	1	2	3	4	5	6
reduced Latin squares (first row and column in order)	1	1	1	4	56	9408
all Latin squares $= n! (n - 1)! \cdot$ reduced	1	2	12	576	161 280	812 851 200

using Square = vector<vector<int>>;
 
// Finite field GF(p^k): elements 0..q-1 are polynomials over Z_p written in base p.
struct GF {
    int p, k, q; vector<vector<int>> add, mul;
    GF(int p, int k) : p(p), k(k), q(1) {
        for (int i = 0; i < k; i++) q *= p;
        auto digits = [&](int x) { vector<int> d(k); for (int i = 0; i < k; i++) d[i] = x % p, x /= p; return d; };
        auto pmul = [&](const vector<int>& a, const vector<int>& b) { vector<int> c(sz(a) + sz(b) - 1); for (int i = 0; i < sz(a); i++) for (int j = 0; j < sz(b); j++) c[i + j] = (c[i + j] + a[i] * b[j]) % p; return c; };
        auto reduce = [&](vector<int> c, const vector<int>& f) {   // c mod monic f of degree k
            for (int i = sz(c) - 1; i >= k; i--) if (int t = c[i]) for (int j = 0; j <= k; j++) c[i - k + j] = ((c[i - k + j] - t * f[j]) % p + p) % p;
            c.resize(k); return c;
        };
        vector<int> f;                                         // monic irreducible of degree k: no nonzero x has x * y = 0
        for (int low = 0; low < q && f.empty(); low++) {
            vector<int> g = digits(low); g.push_back(1); bool ok = true;
            for (int x = 1; x < q && ok; x++) for (int y = 1; y < q && ok; y++) {
                auto r = reduce(pmul(digits(x), digits(y)), g); ok = *max_element(all(r)) > 0;
            }
            if (ok) f = g;
        }
        add.assign(q, vector<int>(q)); mul = add;
        for (int x = 0; x < q; x++) for (int y = 0; y < q; y++) {
            auto a = digits(x), b = digits(y); int s = 0, m = 0;
            auto r = reduce(pmul(a, b), f);
            for (int i = k - 1; i >= 0; i--) s = s * p + (a[i] + b[i]) % p, m = m * p + r[i];
            add[x][y] = s; mul[x][y] = m;
        }
    }
    vector<Square> mols() const {                              // the q - 1 squares L_a(x, y) = a x + y
        vector<Square> res;
        for (int a = 1; a < q; a++) { Square L(q, vector<int>(q)); for (int x = 0; x < q; x++) for (int y = 0; y < q; y++) L[x][y] = add[mul[a][x]][y]; res.push_back(L); }
        return res;
    }
};
 
Square kronecker(const Square& A, const Square& B) {           // order |A| * |B|; preserves orthogonality pairwise
    int a = sz(A), b = sz(B); Square C(a * b, vector<int>(a * b));
    for (int i = 0; i < a * b; i++) for (int j = 0; j < a * b; j++) C[i][j] = A[i / b][j / b] * b + B[i % b][j % b];
    return C;
}
 
bool orthogonal(const Square& A, const Square& B) {
    int n = sz(A); vector<char> seen(n * n, 0);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { int x = A[i][j] * n + B[i][j]; if (seen[x]) return false; seen[x] = 1; }
    return true;
}
 
// Orthogonal mate of L: partition the cells into n disjoint transversals (one cell per row and column, all symbols).
// Returns the mate, or an empty square if none exists.
Square orthogonalMate(const Square& L) {
    int n = sz(L); vector<vector<int>> tr; vector<int> perm(n); iota(all(perm), 0);
    do { int used = 0; bool ok = true; for (int i = 0; i < n && ok; i++) { ok = !(used >> L[i][perm[i]] & 1); used |= 1 << L[i][perm[i]]; } if (ok) tr.push_back(perm); }
    while (next_permutation(all(perm)));
    vector<vector<int>> byFirst(n); for (int t = 0; t < sz(tr); t++) byFirst[tr[t][0]].push_back(t);
    vector<int> colUsed(n, 0), chosen;                         // colUsed[i]: columns of row i already taken
    auto go = [&](auto&& self, int c) -> bool {                // the transversal through cell (0, c)
        if (c == n) return true;
        for (int t : byFirst[c]) {
            bool ok = true; for (int i = 0; i < n && ok; i++) ok = !(colUsed[i] >> tr[t][i] & 1);
            if (!ok) continue;
            for (int i = 0; i < n; i++) colUsed[i] |= 1 << tr[t][i];
            chosen.push_back(t);
            if (self(self, c + 1)) return true;
            chosen.pop_back(); for (int i = 0; i < n; i++) colUsed[i] ^= 1 << tr[t][i];
        }
        return false;
    };
    if (!go(go, 0)) return {};
    Square M(n, vector<int>(n)); for (int s = 0; s < n; s++) for (int i = 0; i < n; i++) M[i][tr[chosen[s]][i]] = s;
    return M;
}

Running orthogonalMate on all 9408 reduced Latin squares of order 6 finds no mate (a few seconds), which settles Euler’s problem.

Proof: at most n - 1 MOLS, and q - 1 for prime powers

Upper bound. Relabelling the symbols of one square keeps it orthogonal to the others, so assume every square has first row $0, 1, \dots, n - 1$ . In each square the cell $(1, 0)$ holds a symbol $\neq = 0$ (the column already has $0$ in row 0). Two different squares cannot hold the same $v$ there: the pair $(v, v)$ would appear both at $(1, 0)$ and at $(0, v)$ . So there are at most $n - 1$ squares.

Field construction. $L_{a} (x, y) = a x + y$ is Latin: for fixed $x$ the map $y \mapsto a x + y$ is a bijection, and for fixed $y$ so is $x \mapsto a x + y$ because $a \neq = 0$ is invertible. For $a \neq = b$ , the pair $(a x + y, b x + y) = (s, t)$ gives $(a - b) x = s - t$ , a unique $x$ , and then a unique $y$ : every pair appears once. The code finds a monic irreducible $f$ of degree $k$ by checking that $Z_{p} [x] / (f)$ has no zero divisors, which is exactly the condition for it to be a field.

Products. If $A ⊥ A^{'}$ (order $a$ ) and $B ⊥ B^{'}$ (order $b$ ), then $A \otimes B ⊥ A^{'} \otimes B^{'}$ : the pair at cell $((i_{1}, i_{2}), (j_{1}, j_{2}))$ is $((A, B), (A^{'}, B^{'}))$ evaluated at $(i_{1}, j_{1})$ and $(i_{2}, j_{2})$ , and as both cell coordinates range over everything, each pair of pairs occurs once. Factoring $n = \prod q_{i}$ into prime powers and taking products of the first $min (q_{i}) - 1$ field squares of each factor gives MacNeish’s bound; if $n \neq \equiv 2 (mod 4)$ , every $q_{i} \geq 3$ , so there are at least two MOLS.

Proof: orthogonal mates are transversal decompositions, and none exists for order 6

If $M ⊥ L$ , the cells where $M = s$ meet each row and column once and (by orthogonality) carry each symbol of $L$ once: a transversal of $L$ . The $n$ symbols of $M$ partition the cells into $n$ disjoint transversals; conversely such a partition defines $M$ by labelling the transversals. orthogonalMate searches this exactly: each transversal contains exactly one cell of row 0, so it picks the transversals through $(0, 0), (0, 1), \dots$ in turn, keeping them disjoint.

Order 6. If some pair $L ⊥ M$ existed, relabel $L$ ‘s symbols so that its first row is $0, 1, \dots, 5$ , then permute the rows of both squares together so that $L$ ‘s first column is $0, 1, \dots, 5$ . Both operations keep the squares Latin and orthogonal, and $L$ is now reduced with a mate. The enumeration produces all 9408 reduced squares (matching the known count), and none has a mate. Mates are not automatic in other orders either: only 1 of the 4 reduced squares of order 4 (the Klein group table) and 6 of the 56 of order 5 have one. The addition table of $Z_{n}$ for even $n$ has no transversal at all: a transversal $σ$ would give $\sum_{i} (i + σ (i)) \equiv 2 \cdot \frac{n ( n - 1 )}{2} \equiv 0 (mod n)$ , while the symbols it covers sum to $\frac{n ( n - 1 )}{2} \equiv \frac{n}{2} (mod n)$ .

Latin rectangles extend. A $k \times n$ Latin rectangle ( $k < n$ ) can always be extended by a row: in the bipartite graph joining column $c$ to the symbols missing from $c$ , every column has degree $n - k$ and every symbol is missing from exactly $n - k$ columns, so the graph is $(n - k)$ -regular and has a perfect matching (Hall / König); the matching is a valid next row. Repeating gives a full Latin square. Checked: all field squares for $q \in {3, 4, 5, 7, 8, 9}$ are pairwise orthogonal, Kronecker products of orthogonal pairs are orthogonal (orders 12, 15, 20), and the reduced-square counts match the table for $n \leq 6$ .

Grid and Matrix Constructions
Sudoku (a solved Sudoku is a Latin square)
Kirkman’s Schoolgirl Problem (another design)
Bipartite Matching (rectangle extension)

whoashish's cp notes

Directory

xliii. Latin Squares and Euler's 36 Officers

Graph View

whoashish's cp notes

Directory

xliii. Latin Squares and Euler's 36 Officers

Related notes

Graph View