# 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