A Latin square is an `n` × `n` array filled with `n` different kinds of object, in which each row and column contains each kind of object only once. For example, below is a 5 × 5 (order 5) Latin square of the integers from 0 to 4:

\left( \begin{array}{ccc}

0 & 1 & 2 & 3 & 4 \\

1 & 4 & 3 & 2 & 0 \\

2 & 3 & 4 & 0 & 1 \\

3 & 0 & 1 & 4 & 2 \\

4 & 2 & 0 & 1 & 3 \end{array} \right)

\)

Latin squares in which the first row and column are in their natural order as above are called *reduced* Latin squares. The number of reduced Latin squares of each order goes 1, 1, 1, 4, 56, 9408, 16942080, … (A000315).

Because of the constraints on the structure of Latin squares, there is no simple algorithm for generating them, but backtracking is an effective way of doing so. Below is a backtracking algorithm in C for generating Latin squares, and a program to generate all squares of order 5:

typedef void (*latin_squarefn)(const unsigned int*, unsigned int); /* Get the cell index at a specified row and column in the Latin square */ unsigned int get_cell(int n, int row, int column) { return (row - 1) * (n - 1) + column - 1; } /* Get the row for an array cell */ unsigned int get_row(unsigned int cell, unsigned int n) { return cell / (n - 1) + 1; } /* Get the column for an array cell */ unsigned int get_column(unsigned int cell, unsigned int n) { return cell % (n - 1) + 1; } /* Check that there are no conflicts */ static unsigned int promising(unsigned int i, const unsigned int *square, unsigned int n) { unsigned int row, column; unsigned int ok = 1; unsigned int cell; /* Check row */ row = get_row(i, n); ok = square[i] != row; /* Row header */ if (!ok) { return 0; } column = 1; cell = get_cell(n, row, column); while (cell < i && ok) { ok = square[cell] != square[i]; column++; cell = get_cell(n, row, column); } if (!ok) { return 0; } /* Check column */ column = get_column(i, n); ok = square[i] != column; /* Column header */ if (!ok) { return 0; } row = 1; cell = get_cell(n, row, column); while (cell < i && ok) { ok = square[cell] != square[i]; row++; cell = get_cell(n, row, column); } return ok; } static void latin_squares_recursive(int i, unsigned int *square, unsigned int n, latin_squarefn fun) { const size_t size = (n - 1) * (n - 1); if (i < 0 || promising(i, square, n)) { if (i == size - 1) { fun(square, n); } else { unsigned int val; for (val = 0; val < n; val++) { square[i + 1] = val; latin_squares_recursive(i + 1, square, n, fun); } } } } void latin_squares(unsigned int n, latin_squarefn fun) { if (n <= 1) { return; } unsigned int *square = calloc((n - 1) * (n - 1), sizeof(unsigned int)); if (square == NULL) { return; } latin_squares_recursive(-1, square, n, fun); free(square); } static void print(const unsigned int *square, unsigned int n) { unsigned int row, col, cell = 0; for (col = 0; col < n; col++) { printf("%d ", col); } putchar('\n'); for (row = 1; row < n; row++) { printf("%d ", row); for (col = 1; col < n; col++) { printf("%d ", square[cell]); cell++; } putchar('\n'); } putchar('\n'); } int main(void) { latin_squares(5, print); return 0; }