Tag Archives: Latin square

Partial Latin square completion using backtracking in C

The partial Latin square completion problem is to take a partially-filled Latin square and to determine if it can be completed successfully. For example, below is a 1-based order 5 partial Latin square:

\(
\left( \begin{array}{ccc}
\cdot & 2 & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & \cdot & 3 \\
\cdot & \cdot & 5 & \cdot & \cdot \\
4 & \cdot & \cdot & \cdot & \cdot \\
\cdot & \cdot & \cdot & 2 & \cdot \end{array} \right)
\)

 

The problem is to find out if it can be completed, which in this case it can, to this square:

\(
\left( \begin{array}{ccc}
1 & 2 & 3 & 4 & 5 \\
2 & 1 & 4 & 5 & 3 \\
3 & 4 & 5 & 1 & 2 \\
4 & 5 & 2 & 3 & 1 \\
5 & 3 & 1 & 2 & 4 \end{array} \right)
\)

 

The partial Latin square completion problem is NP-complete, but can be solved using backtracking.

Here is an implementation in C. It takes a partial Latin square in the form of a 1-dimensional array, with 0s for the unfilled cells, and a callback function which is called with the solution, if found.

#include <stdlib.h>

static void get_row_column(unsigned int cell, unsigned int *row, unsigned int *column, size_t size)
{
    *row = cell / size;
    *column =  cell % size;
}

static unsigned int get_value(const unsigned int *square, size_t size, unsigned int row,
        unsigned int column)
{
    return square[row * size + column];
}

static unsigned int unique_in_column(const unsigned int *square, size_t size, unsigned int cell)
{
    unsigned int row;
    unsigned int column;
    get_row_column(cell, &row, &column, size);
    unsigned int r;
    unsigned int unique = 1;
    for (r = 0; r < size && unique; r++) {
        unique = r == row || get_value(square, size, r, column) != square[cell];
    } 
    return unique;
}

static unsigned int unique_in_row(const unsigned int *square, size_t size, unsigned int cell)
{
    unsigned int row;
    unsigned int column;
    get_row_column(cell, &row, &column, size);
    unsigned int c;
    unsigned int unique = 1;
    for (c = 0; c < size && unique; c++) {
        unique = c == column || get_value(square, size, row, c) != square[cell];
    } 
    return unique;
}

static unsigned int promising(const unsigned int *square, size_t size, unsigned int cell)
{
    return square[cell] == 0
        || (unique_in_row(square, size, cell)
                && unique_in_column(square, size, cell));
}

static unsigned int get_next_cell(const unsigned int *square, size_t size, unsigned int *cell)
{
    unsigned int found = 0;
    unsigned int i;
    for (i = *cell; i < size * size && !found; i++) {
        if (square[i] == 0) {
            found = 1;
            *cell = i;
        }
    }
    return found;
}

static void latin_square_completion_recursive(unsigned int *square, size_t size, unsigned int cell,
        unsigned int *succeeded, latin_square_completionfn fun)
{
    if (!get_next_cell(square, size, &cell)) {
        *succeeded = 1;
        fun(square, size);
    }
    else {
        unsigned int i;
        for (i = 1; i <= size && !*succeeded; i++) {
            unsigned int temp = square[cell];
            square[cell] = i;
            if (promising(square, size, cell)) {
                latin_square_completion_recursive(square, size, cell + 1, succeeded, fun);
            }
            square[cell] = temp;
        }
    }
}

void latin_square_completion(unsigned int *square, size_t size,
        latin_square_completionfn fun)
{
    unsigned int cell = 0;
    unsigned int succeeded = 0;
    latin_square_completion_recursive(square, size, cell, &succeeded, fun);
}

Here is a program to complete the partial Latin square shown at the beginning:

#include <stdio.h>

static void print(const unsigned int *square, size_t size)
{
    unsigned int i;
    for (i = 0; i < size * size; i++) {
        printf("%d ", square[i]);
        if (i % size == size - 1) {
            printf("\n");
        }
    }
    printf("\n");
}

int main(void)
{
    unsigned int square[] = {0, 2, 0, 0, 0,
                             0, 0, 0, 0, 3,
                             0, 0, 5, 0, 0,
                             4, 0, 0, 0, 0,
                             0, 0, 0, 2, 0};
    latin_square_completion(square, 5, print);
    return 0;
}

The output:

1 2 3 4 5
2 1 4 5 3
3 4 5 1 2
4 5 2 3 1
5 3 1 2 4

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