Latin squares with backtracking in C

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;
}