Latin Squares

A Latin square is a square of nxn fields, whereby every field contains one of n different symbols. Every symbol appears in every row and every column exactly once. The number n is referred to as the "order" of the Latin square.

An order-9 Latin square with the additional condition that all the symbols each occur only once in the nine 3x3 sub-squares present gives rise to the number puzzle Sudoku.

A Graeco-Latin square can be constructed from two Latin squares if the ordered n^2 pairs obtained via the combination occur only once. In this instance, the Latin squares are said to be orthogonal. Graeco-Latin squares are also known as Euler squares.  

History

The mathematician Leonhard Euler studied these squares intensively. He used the Latin and Greek alphabets as symbols – hence the names. Euler devised methods for the construction of Graeco-Latin squares of an odd order and the order 4k, for k = 1, 2, ... In 1779 he also considered the thirty-six officers problem, which was supposed to lead to the construction of an order-6 Graeco-Latin square. As this is impossible and there is no order-2 Graeco-Latin square, either, he suspected that no Graeco-Latin square of the order 4k + 2, for k = 0, 1, ... could exist. His assertion was refuted by the discovery of counter-examples in 1959 and, in 1960, R.C. Bose, E.T. Parker and S.S. Shrikhande published a paper proving that Graeco-Latin squares of the 4k + 2, for k = 2, 3, ... do actually exist.

Mathematics

A Latin square for any order n is easy to construct. The question as to the existence of Graeco-Latin squares of the order n is much more complex. It has been proven that there is a maximum of n – 1 paired orthogonal Latin squares of the order n. The existence of this maximum number is equivalent to the existence of a finite projective plane of the order n.