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