Eulerian Squares

An Eulerian square is a square array of ordered pairs such that the first elements of each ordered pair form a Latin square (an n × n matrix of n elements, with no element occurring more than once within any row or column of the matrix), the second elements of each ordered pair also form a Latin square, and each of the ordered pairs is unique. As an example, the following is an order-4 Eulerian square:

(3,3)	(2,2)	(1,1)	(0,0)
(0,1)	(1,0)	(2,3)	(3,2)
(2,0)	(3,1)	(0,2)	(1,3)
(1,2)	(0,3)	(3,0)	(2,1)

If you study the above square, you will notice that the first elements and second elements of each pair form two Latin squares, and that each of the 16 possible ordered pairs from (0,0) to (3,3) occurs exactly once.

You can create an Eulerian square if you can find two Latin squares for which the ordered pairs formed by juxtaposing the two squares are all different—in other words, if the two Latin squares are are orthogonal. For example, the two following Latin squares are orthogonal:

3	2	1
2	1	3
1	3	2

2	3	1
1	2	3
3	1	2

These can be combined into the following Eulerian square:

(2,1)	(1,2)	(0,0)
(1,0)	(0,1)	(2,2)
(0,2)	(2,0)	(1,1)

There is a relationship between Eulerian squares and magic squares. If the n elements are each 0 through n − 1, then if we take each ordered pair and replace it with (1 + the second element + n times the first element), where n is the dimension of the square, we get a semi-magic square. For example, we can transform the Eulerian square above into the following semi-magic square:

1 + 3 × 2 + 1 = 8	1 + 3 × 1 + 2 = 6	1 + 3 × 0 + 0 = 1
1 + 3 × 1 + 0 = 4	1 + 3 × 0 + 1 = 2	1 + 3 × 2 + 2 = 9
1 + 3 × 0 + 2 = 3	1 + 3 × 2 + 0 = 7	1 + 3 × 1 + 1 = 5

Note that the square are usually only semi-magic, because the diagonals do not always sum to the magic constant.

As the name suggests, Eulerian squares were studied by Leonhard Euler. He posed the following problem, often referred to as the 36 officers problem: Six army regiments are each represented by six officers—one colonel, one lieutenant-colonel, one major, one captain, one lieutenant, and one ensign. Is it possible to have the 36 officers stand in a square such that each row and each column has exactly one representative of each regiment and exactly one representative of each rank? This problem is equivalent to finding a 6 × 6 Eulerian square. Euler was not able to find a solution for this problem, and he conjectured in 1782 that no Eulerian squares of order 4k + 2 exist, where k = 0, 1, 2, 3, ... In other words, no Eulerian squares of orders 2, 6, 10, 14, and so on exist. It is easy to see that no Eulerian squares of order 2 exist, and in 1900 it was proved that no order 6 Eulerian squares exist and hence that the 36 officers problem cannot be solved. However, in 1959 it was shown that Eulerian squares exist for every other order, showing that Euler's conjecture was false.