# Euler Squares

## Introduction

With the recent popularization of Sudoku, interest in related mathematical games such as magic squares and Latin squares has also been revived. Sudoku puzzles are a special case of Latin squares; in fact any solution to a Sudoku puzzle is a Latin square. A Latin square is a square grid filled with symbols in such a way that each symbol occurs once and only once in each row or column. For example, a 3x3 Latin square would have nine cells in which three distinct symbols would be arranged in a way such that no symbol is repeated horizontally or vertically (see Figure 1).

 A B C B C A C A B

Figure 1: 3x3 Latin square

Latin squares were known by early Arabic numerologists. These mystical squares, known as wafq majazi, were found on 13th century Islamic amulets [1] and sketched in the margins of a 16th century Arabic medical text [2]. The famous Swiss mathematician Leonhard Euler wrote about Latin squares in his paper Recherches sur une nouvelle espece de Quarres Magiques in 1782. More recently, Arthur Cayley (1821-1892), Ronald A. Fisher (1890-1962), and others have applied Latin squares in the fields of agronomy, computer science, number theory, graph theory, coding theory, and the design and statistical analysis of scientific experiments [3] [4] [5].

## Euler Squares

Euler squares are created when two orthogonal Latin squares are overlaid to include two attributes in each cell of the array. Orthogonal Latin squares ensure that each and every possible pairing of the two attributes appears exactly once in the array. Now known as Graeco-Roman squares or Euler squares, these arrays are classified by their “order”, or the number of items along one side of the square array. For example, a 3x3 Euler square has order three.

In 1694, Jacques Ozanam [6] posed the problem of arranging 16 playing cards in a 4 x 4 array such that no row or column contained more than one card of each suit and each rank (Figure 2).  The solution forms an Euler square of order four with the attributes ofcard rank and suit.  There are 144 possible solutions, not including symmetrical transformations [7].

Figure 2:  One solution to the playing card problem

## Euler's Officer Problem

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

## Solving Euler Squares of Order Five

Euler squares were introduced on the first day of a problem solving class for mathematics teachers. Nineteen teachers were placed in collaborative groups and given a pegboard holding five different geometric shapes in five different colors (see Figure 4). The author acknowledges ETA Cuisenaire for providing the six Geo-Shapes Pegboards for her research.

Figure 4: A Geo-Shapes Pegboard

Challenged to find a way to place the pegs so that no shape or color repeated in any row or column, groups were observed using three methods to find a solution: diagonalization (shown above in Figure 4), the knight’s move, and Sudoku skills.

## Diagonalization

Placing a single color down a main diagonal of the pegboard begins this method. Then place another color on a parallel diagonal, noting this will leave a single peg of that color to be placed in the opposite corner. Continue to diagonalize by color. This is an eye-pleasing and symmetrical solution. Double diagonalization can be accomplished by placing color on one main diagonal and shape on the other second diagonal (see Figure 5).

Figure 5: Double diagonalization solution

## Knight's Move

Referring to Figure 6, place pegs of one shape (star) down a main diagonal. Beginning with the corner color (pink), choose another shape (circle) and place that color on the pegboard by counting out the knight’s move in chess, over two and up one. Continue placing shapes (square, hexagon, and triangle) of the same color using the knight’s move, “wrapping” around behind the board when necessary (see arrows in Figure 6). Continue placing shapes in the same order, ensuring that colors are placed on the knight’s move. This method also produces diagonalization by shape but incorporates a new color pattern.

Figure 6:  Wrapping around using the knight's move

## Sudoku Skills

Skills learned in solving Sudoku puzzles can be applied to solving the Euler square. However, this is not an easy method, and is probably best applied after beginning with the two methods above. Randomly place pegs on diagonals or rows, and then continue by choosing a spot on the array and eliminating already used colors and shapes for that row and column. Now choose wisely from the remaining pegs, adjusting when necessary. At times the last color or last shape can be placed by checking which row or column does not yet have that attribute. This solution method was more random and did not evince diagonalization or symmetry (see Figure 7).

Figure 7:  Using Sudoku skills to place the last red peg

## Discourse and Extension

Comparing solutions and methods between groups led teachers to realize that there were multiple solutions and multiple methods for solving Euler squares. The instructor then challenged groups to determine how many possible solutions there might be using their particular method. Groups using diagonalization speculated on the permutations of their current design, and discussed which were rotations or reflections and whether these patterns counted as unique.

Another group began to extend their exploration by creating a table of Euler squares of increasing order. They soon discovered that an Euler square of order two was impossible to make. However, using only one attribute, they found there were two Latin squares. They moved on to Euler squares of higher order and began counting how many solutions existed. By the end of the class period they were trying to identify a formula to predict the number of solutions as well as wondering why a 6x6 Euler square did not exist.

A simple child’s toy and an intriguing historical problem can be combined to encourage problem solving. Teachers not only learned about Euler squares and related mathematical topics, they learned a lot about themselves and their own thinking abilities. The accompanying Flash module will allow the reader to engage in this historical problem.

## Questions and Resources

Questions for Investigation

1.  Find a Latin square of order two. How many different ones are there?

2.  Prove to yourself that an Euler square of order two does not exist.

3.  Find a Latin square of order six.

Online Resources

Teddy Town is an interactive game of Latin squares for 6-7 year olds.

4x4 Euler square shapes can be printed and cut out to create a game.  See for the the accompanying article and instructions.

Constructing orthogonal Latin squares is an applet by Alexander Bogomolny.

## Bibliography

[1] Singmaster, D. (1998). Chronology of Recreational Mathematics. Retrieved September 2, 2006 from http://www.eldar.org/~problemi/singmast/recchron.html

[2] U.S. National Library of Medicine. (2006). Islamic Medical Manuscripts. Retrieved September 2, 2006 from http://www.nlm.nih.gov/hmd/arabic/

[3] Emanouilidis, E. (2005). Latin and magic squares. International Journal of Mathematical Education in Science and Technology, 36(5), 546-9.

[4] Petersen, I. (2000). Completing Latin squares. Science News Online, 157(19). Retrieved September 2, 2006 from http://www.sciencenews.org/articles/20000506/mathtrek.asp

[5] D'enes, J., & Keedwell, A.D. (1974). Latin Squares and their Applications. New York: Academic Press.

[6] Ozanam, J. (1694). Récréations mathématiques et physiques. Paris: Charles-Antoine Jombert.

[7] Pais, J., & Singer, R. (2004). Visual Magic Squares and Group Orbits I. Retrieved October 14, 2006 from http://www.mi.sanu.ac.rs/vismath/pais/pais.html

[8] Sharp, J. (2005). Beyond Su Doku. Infinity, 1(3). Reprinted in Mathematics Teaching in the Middle School, 12(3), 165-169.

[9] Bose, R.C., Shrikhande, S.S., & Parker, E.T. (1960). Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler's conjecture. Canadian Journal of Mathematics, 12, 189-203.