Latin Square

A Latin square is a square grid of size $ n \times n $ filled with $ n $ distinct symbols (letters, numbers, or others). The main rule is as follows: each symbol must appear exactly once in each row and exactly once in each column.

There are several methods for generating Latin squares. Here is the shortest to explain:

1- Take an empty NxN grid,

2- Fill the first row with N symbols

3- Fill the next row by shifting all the symbols by 1 box to the right (and return to the beginning of the row if necessary)

4- Repeat step 3 until you reach the last row of the grid.

And voilà! The square is thus valid but always identical, to obtain others:

5- Randomly swap 2 rows

6- Randomly swap 2 columns

7- Repeat steps 5 and 6 as many times as desired, the result is always a Latin square.

Solving a Latin square can be summarized in one loop:

1- For each empty cell, determine the symbols that are not already present in the row and column.

2- If only one symbol is possible, the cell can be filled immediately with that symbol.

3- Repeat step 1 until the grid is complete.

For more complex grids, algorithmic methods are used, such as backtracking, which tests different possibilities while respecting the constraints.

The term Latin square was introduced by the Swiss mathematician Leonhard Euler in the 18th century. In his work, Euler used letters of the Latin alphabet as symbols to fill the grids.

The 36 Officers Problem, posed by Euler in 1782, asks whether it is possible to arrange 36 officers belonging to 6 different regiments and 6 different ranks in a 6 × 6 grid such that each row and each column contains every regiment and every rank exactly once. This problem is equivalent to finding two orthogonal Latin squares of order 6 (also called Graeco-Latin squares). It was proven in the 20th century that such a configuration is impossible.

The best known variant is sudoku, which uses the same bases, but adds a constraint on blocks of 3x3 (and sometimes other constraints for irregular sudoku).

Ken-ken (kendoku) is also a Latin square with constraints of mathematical calculations.

The magic square is a distant mathematical variant which takes up the fact that the sum of the rows and the columns is always identical, but it is not limited to N distinct symbols.

The number of possible Latin squares increases rapidly with the size of $ N $. For $ N = 3 $ there are 12 different Latin squares, for $ N = 4 $ there are 576, then 161280 for 5, 812851200 for 6 etc. for larger sizes this number becomes exponential, see here

There is currently no simple formula that allows this number to be calculated directly for any $ N $.

Latin squares were systematically studied by the mathematician Leonhard Euler in 1782 (18th century). However, similar structures were probably used long before.