Euler Squares - Euler's Officer Problem

Elaine Young

In 1779, Euler examined the now famous officer problem [8]

Six different regiments have six officers, each one belonging to different ranks. Can these 36 officers be arranged in a square formation so that each row and column contains one officer of each rank and one of each regiment?

Euler conjectured that there was no solution to this problem, or for any other Euler square of order 4n+2. This famous conjecture stood for over 100 years until Gaston Tarry, a French mathematician, proved the non-existence of the order six square by exhausting all possible arrangements by hand in 1901. In 1960, Parker, Bose and Shrikhande [9] used a computer to create an Euler square of order ten and subsequently proved that the only impossible Euler squares were of order two and six. An example of an Euler square of order ten can be seen here. An Euler square of order three is shown below with the dual attributes of symbol and color. The three symbols and three colors are placed so that no symbol or color is repeated in any given row or column. This Euler square can be decomposed into two Latin squares, one with the three symbols and the other with the three colors (see Figure 3).

Figure 3: An Euler square decomposed into two Latin squares