# Latin Squares in Practice and in Theory II

Alex Bogomolny's *Cut The Knot!* website has a page on
Orthogonal
Latin Squares with some nice examples using the Galois field of
order 4. There is a nice article by Edythe Parker Woodruff about her brother
E. T. Parker's work on the ``Euler conjecture.'' Rob Beezer's
Graeco-Latin Squares
page shows a `10x10` ``Euler spoiler.'' The survey article
by Charles Colbourn and Jeff Dinitz, from which the table of lower
bounds on `N(n)` is reproduced, is available
online.

## 1. Leonhard Euler's Puzzle of the 36 Officers

*Une question fort curieuse* is the way Euler introduces
this puzzle. It involves 36 officers from six regiments. In this
illustration we will distinguish the regiments by their colors:
black, red, blue, green, purple and brown. Each regiment is
represented by officers of six different ranks, which here
we will characterize as King, Queen, Rook, Bishop, Knight, Pawn.
Here they are (set in Eric Bentzen's Chess Alpha):

Ther problem is to line them up in a six by six array so
that each row and each column holds one officer of each
rank and one officer from each regiment.

Try it. It's impossible.

But if we replace ``six'' with ``five''

or with ``seven'' (adding yellow as the extra regiment and
Joker as the extra rank)

the problem can be solved, as shown.

What is the matter with six? It's not just that it is
composite, because the problem can be solved for 4, 8
and 9, and in fact for *any* number besides 2
(obviously impossible) and 6. Euler did not actually prove that
6 was impossible. (*Or, après toutes les peines
qu'on s'est données pour résoudre ce problème,
on a été obligé de reconnoître
qu'un tel arrangement est absolument impossible, quoiqu'on
ne puisse pas en donner de démostration rigoureuse.*)
The proof waited from 1782 until 1900,
when it was worked out by G. Tarry. Euler did show that
there was a solution for any number of regiments
(and of ranks) not of the form `4s+2`. He
remarked that his method does not work for numbers of that form.
After his death, this remark metamorphosed into a conjecture
that there was no solution for those numbers; the conjecture
lived on until 1959 when E. T. Parker, R. C. Bose and S. Shrikhande,
working separately and then together, showed that it was
false for all `s` greater than one.

In this column we will explore the topic of *mutually
orthogonal latin squares,* the modern
setting for the problem of the officers and its generalizations.

--*Tony Phillips*

Stony Brook