Tag Archives: Backtracking

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

N-Queens with backtracking in C

The n-queens problem is to place n queens on an n × n chessboard such that no two queens threaten each other by sharing the same row, column, or diagonal. For the usual 8 × 8 chessboard, there are \({64 \choose 8}\) = 4,426,165,368 ways of placing the queens, but only 92 solutions. This is a classic problem for a backtracking algorithm.

typedef void(*queenfn)(unsigned int *, size_t);

static unsigned int promising(unsigned int *board, int i, size_t n)
{
    int j;
    unsigned int ok = 1;
    for (j = 0; j < i && ok; j++) {
        if (board[i] == board[j] || abs((int)board[i] - (int)board[j]) == i - j) {
            ok = 0;
        }
    }
    return ok;
}

static void n_queens_recursive(unsigned int *board, int i, size_t n, queenfn fun)
{
    if (promising(board, i, n)) {
        if (i == (int)n - 1) {
            fun(board, n);
        }
        else if (i < (int)n - 1) {
            unsigned int square;
            for (square = 0; square < n; square++) {
                board[i + 1] = square;
                n_queens_recursive(board, i + 1, n, fun);
            }
        }
    }
}

void n_queens(size_t n, queenfn fun)
{
    unsigned int *board = malloc(n * sizeof(unsigned int));
    if (board == NULL) {
        return;
    }
    n_queens_recursive(board, -1, n, fun);
    free(board);
}

void print(unsigned int *board, size_t n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%d ", board[i]);
    }
    printf("\n");
}

int main(void)
{
    const unsigned int n = 8;
    n_queens(n, print);
    return 0;
}

Vertex colouring with backtracking in C

The vertex colouring problem is to colour the vertices of a graph in such a way that no two adjacent vertices are the same colour. The decision problem of whether a graph can be coloured in m or fewer colours is NP-complete.

Although the problem is intractable, a bactracking algorithm can be used to reduce the number of colourings that need to be tried. The algorithm works by colouring the vertices one at a time, and backtracking if at any point it becomes impossible to colour the next vertex differently from all of its neighbours.

typedef void(*vertex_colouringfn)(const unsigned int *, size_t);

static unsigned int promising(int i, const unsigned int **adjmat, const unsigned int *colours)
{
    int j;
    unsigned int ok = 1;

    for (j = 0; j < i && ok; j++) {
        if (adjmat[i][j] && colours[i] == colours[j]) {
            /* Adjacent vertex is the same colour */
            ok = 0;
        }
    }
    return ok;
}

static void vertex_colouring_recursive(int i, const unsigned int **adjmat, size_t len,
        unsigned int *colours, unsigned int m, vertex_colouringfn fun)
{
    unsigned int colour;

    if (promising(i, adjmat, colours)) {
        if (i == len - 1) {
            /* Coloured every vertex successfully */
            fun(colours, len);
        }
        else if (i < (int)len - 1) {
            /* Try every colour for the next vertex */
            for (colour = 0; colour < m; colour++) {
                colours[i + 1] = colour;
                vertex_colouring_recursive(i + 1, adjmat, len, colours, m, fun);
            }
        }
    }
}

void vertex_colouring(const unsigned int **adjmat, size_t len, unsigned int m, 
        vertex_colouringfn fun)
{
    unsigned int *colours = calloc(len, sizeof(unsigned int));
    if (colours == NULL) {
        return;
    }
    vertex_colouring_recursive(-1, adjmat, len, colours, m, fun);
    free(colours);
}

This is an example program with a small graph and m = 3:

static void print_colouring(const unsigned int *colours, size_t len)
{
    unsigned int i;
    for (i = 0; i < len; i++) {
        printf("%d ", colours[i]);
    }
    printf("\n");
}

int main(void)
{
    unsigned int v0[] = {0, 1, 1, 1, 0};
    unsigned int v1[] = {1, 0, 1, 0, 1};
    unsigned int v2[] = {1, 1, 0, 1, 1};
    unsigned int v3[] = {1, 0, 1, 0, 1};
    unsigned int v4[] = {0, 1, 1, 1, 0};
    const unsigned int *adjmat[] = {v0, v1, v2, v3, v4};
    const size_t len = sizeof(adjmat) / sizeof(unsigned int*);
    const unsigned int m = 3; /* Number of colours */
    vertex_colouring(adjmat, len, m, print_colouring);
    return 0;
}

xkcd 287

General solutions get you a 50% tip

I’m not sure what this problem is called – I’m going to call it "multicombination sum" – but I don’t doubt that it is NP-complete, as it’s a variety of knapsack problem in which the values of the items are the same as their weight.

Below are three methods of solving it: a brute force method, using backtracking, and using dynamic programming.

Brute force method

The brute force method is just to construct all of the possible orders that might total $15.05.
The combinatorial algorithm we want is combinations with duplicates, or multicombinations.
Since 3 of the most expensive appetizer – SAMPLER PLATE – exceeds the target, and 7 of the cheapest appetizer – MIXED FRUIT – equals the target (so that’s one of the solutions), we want to iterate over all multicombinations with k ranging from 3 to 7.

unsigned int multiset_sum(const unsigned int *multiset, const unsigned int *values, unsigned int k)
{
    unsigned int i;
    unsigned int sum = 0;
    for (i = 0; i < k; i++) {
        sum += values[multiset[i]];
    }
    return sum;
}

typedef void (*multiset1fn)(const unsigned int *, unsigned int);

void multicombination_sum(const unsigned int *items, size_t len, unsigned int target,
        multiset1fn fun)
{
    unsigned int first = target / array_max(items, len);
    unsigned int last = target / array_min(items, len);
    unsigned int *multiset = calloc(last + 1, sizeof(unsigned int));
    unsigned int k;
    if (!multiset) {
        return;
    }
    for (k = first; k <= last; k++) {
        do {
            if (multiset_sum(multiset, items, k) == target) {
                fun(multiset, k);
            }
        } while (next_multicombination(multiset, len, k));
    }
    free(multiset);
}

void order_print(const unsigned int *numbers, unsigned int k)
{
	const char *appetizers[] = {"MIXED FRUIT", "FRENCH FRIES", "SIDE SALAD", 
        "HOT WINGS", "MOZARELLA STICKS", "SAMPLER PLATE"};
    unsigned int i, item, count;
    for (i = 0; i < k; i++) {
        if (i == 0 || numbers[i] != item) {
            if (i > 0) {
                printf("%s (x%d) ", appetizers[item], count);
            }
            count = 1;
            item = numbers[i];
        }
        else {
            count++;
        }
    }
    printf("%s (x%d)\n", appetizers[item], count);
}

int main(void)
{
    unsigned int prices[] = {215, 275, 335, 355, 420, 580};
	const size_t n = sizeof(prices) / sizeof(prices[0]);
    const unsigned int target = 1505;
    multicombination_sum(prices, n, target, (multiset1fn)order_print);

	return 0;
}

Output:

MIXED FRUIT (x1) HOT WINGS (x2) SAMPLER PLATE (x1)
MIXED FRUIT (x7)

This took 1709 iterations to come up with the answer.

Backtracking

We can drastically reduce the search space by building the orders up one item at a time, and backtracking if the target is exceeded.


typedef void(*multiset2fn)(unsigned int *, const unsigned int *, size_t); 

static void multicombination_sum_recursive(int i, unsigned int *combination, 
       const unsigned int *items, size_t len, unsigned int target, multiset2fn fun,
       unsigned int sum)
{
    if (i == (int)len - 1) {
        if (sum == target) {
            fun(combination, items, i);
        }
    }
    else  {
        unsigned int quantity;
        unsigned int max_quantity = (target - sum) / items[i + 1];
        for (quantity = 0; quantity  <= max_quantity; quantity++) {
            combination[i + 1] = quantity;
            multicombination_sum_recursive(i + 1, combination, items, len, target, fun, 
                    sum + quantity * items[i + 1]);
        }
    }
}

void multicombination_sum(const unsigned int *items, size_t len, unsigned int target,
        multiset2fn fun)
{
    unsigned int *combination = malloc(len * sizeof(unsigned int));
    multicombination_sum_recursive(-1, combination, items, len, target, fun, 0);
    free(combination);
}

void order_print(const unsigned int *combination, const unsigned int *items, size_t len)
{
    const char *appetizers[] = {"MIXED FRUIT", "FRENCH FRIES", "SIDE SALAD", 
        "HOT WINGS", "MOZARELLA STICKS", "SAMPLER PLATE"};
    unsigned int i;
    for (i = 0; i <= len; i++) {
        if (combination[i] > 0) {
            printf("%s (x%d) ", appetizers[i], combination[i]);
        }
    }
    putchar('\n');
}

int main(void)
{
    unsigned int prices[] = {215, 275, 335, 355, 420, 580};
    const unsigned int len = sizeof(prices) / sizeof(unsigned int);
    const unsigned int target = 1505;
    multicombination_sum(prices, len, target, (multiset2fn)order_print);
    return 0;
}

Output:

MIXED FRUIT (x1) HOT WINGS (x2) SAMPLER PLATE (x1)
MIXED FRUIT (x7)

This took just 211 iterations.

Dynamic Programming

As I said at the beginning, this problem is a special case of the knapsack problem in which the values of the items are the same as their weight. This means that we can use the classic dynamic programming algorithm for knapsack to solve it. The algorithm works by calculating the most profitable knapsack for each capacity up to the target capacity.

Here is an implementation of the algorithm:

struct knapsack {
    unsigned int profit;
    struct knapsack *prev;
};
typedef struct knapsack knapsack;

/* Find the minimum weight item with this profit */
int min_weight_item(unsigned int profit, const unsigned int *weights, const unsigned int *profits,
        size_t len)
{
    int item = -1;
    unsigned int i;
    for (i = 0; i < len; i++) {
        if (profits[i] == profit) {
            if (item == -1 || weights[i] < weights[item]) {
                item = i;
            }
        }
    }
    return item;
}

unsigned int unbounded_knapsack(unsigned int capacity, unsigned int *weights, 
       unsigned int *profits, unsigned int *counts, size_t len)
{
    knapsack *z = malloc((capacity + 1) * sizeof(knapsack));
    unsigned int c, i;
    unsigned int solution, profit;
    z[0].profit = 0;
    z[0].prev = NULL;
    knapsack *current;
    /* Fill in the array */
    for (c = 1; c <= capacity; c++) {
        z.profit = z.profit;
        z.prev = &(z);
        for (i = 0; i < len; i++) {
            if (weights[i] <= c) {
                knapsack *prev = z + (c - weights[i]);
                if (prev->profit + profits[i] > z.profit) {
                    z.profit = prev->profit + profits[i];
                    z.prev = prev;
                }
            }
        }
    }
    /* Read back the best solution */
    for (profit = z[capacity].profit, current = z[capacity].prev;
            current != NULL;
            profit = current->profit, current = current->prev) {
        counts[min_weight_item(profit - current->profit, weights, profits, len)]++;
        
    }
    solution = z[capacity].profit;
    free(z);
    return solution;
}

We just need to use this algorithm and pass the prices of the menu items for both weights and profits:

int main(void)
{
    unsigned int values[] = {215, 275, 335, 355, 420, 580};
    const size_t len = sizeof(values) / sizeof(values[0]);
    unsigned int counts[6] = {0};
    const unsigned int target = 1505;
    unbounded_knapsack(target, values, values, counts, len);
    order_print(counts, len);
    return 0;
}

This produces one of the solutions:

MIXED FRUIT (x7)

We could modify the algorithm to produce all of them.