Tag Archives: Backtracking

0-1 Knapsack using backtracking in C

In the 0-1 Knapsack problem, we are given a set of items with individual weights and profits and a container of fixed capacity (the knapsack), and are required to compute a loading of the knapsack with items such that the total profit is maximised. We only have 1 of each item, so there is either 0 or 1 of each item in in the knapsack, hence the 0-1 in the name of the problem.

The 0-1 knapsack problem is NP-hard, but can be solved quite efficiently using backtracking. Below is a backtracking implementation in C. The function knapsack() takes arrays of weights, and profits, their size, the capacity, and the address of a pointer through which the solution array is returned. It returns the profit of the best knapsack. The profit density of each item (weight / profit) is first calculated, and the knapsack is filled in order of decreasing profit density. A bounding function is used to determine the upper bound on the profit achievable with the current knapsack so as to reduce the search space.

#include <stdlib.h>
#include <string.h>

/* A knapsack item */
typedef struct {
    unsigned int id;
    double weight;
    double profit;
    double profit_density;
} item;

/* Compare items by lesser profit density */
static int compare_items(const item *item1, const item *item2)
{
    if (item1->profit_density > item2->profit_density) {
        return -1;
    }
    if (item1->profit_density < item2->profit_density) {
        return 1;
    }
    return 0;
}

/* Bounding function */
static double profit_bound(const item *items, size_t n, double capacity,
        double current_weight, double current_profit,
        unsigned int level)
{
    double remaining_capacity = capacity - current_weight;
    double bound = current_profit;
    unsigned int lvl = level;
    /* Fill in order of decreasing profit density */
    while (lvl < n &&
        items[lvl].weight <= remaining_capacity) 
    {
        remaining_capacity -= items[lvl].weight;
        bound += items[lvl].profit;
        lvl++;
    }
    /* Pretend we can take a fraction of the next object */
    if (lvl < n) {
        bound += items[lvl].profit_density
            * remaining_capacity;
    }
    return bound;
}

static void knapsack_recursive(const item *items, size_t n, double capacity,
        unsigned int *current_knapsack, double *current_weight, double *current_profit,
        unsigned int *max_knapsack, double *max_profit, unsigned int level)
{   
    if (level == n) {
        /* Found a new max knapsack */
        *max_profit = *current_profit;
        memcpy(max_knapsack, current_knapsack, n * sizeof(unsigned int));
        return;
    }
    if (*current_weight + items[level].weight <= capacity)
    {   /* Try adding this item */
        *current_weight += items[level].weight;
        *current_profit += items[level].profit;
        current_knapsack[items[level].id] = 1;
        knapsack_recursive(items, n, capacity, current_knapsack, current_weight, 
                current_profit, max_knapsack, max_profit, level + 1);
        *current_weight -= items[level].weight;
        *current_profit -= items[level].profit;
        current_knapsack[items[level].id] = 0;
    }
    if (profit_bound(items, n, capacity, *current_weight, 
                *current_profit, level + 1) > *max_profit) {
        /* Still promising */
        knapsack_recursive(items, n, capacity, current_knapsack, current_weight, 
                current_profit, max_knapsack, max_profit, level + 1);
    }
}

double knapsack(const double *weights, const double *profits, 
        size_t n, double capacity, unsigned int **max_knapsack)
{
    double current_weight = 0.0;
    double current_profit = 0.0;
    double max_profit = 0.0;
    unsigned int i;
    item *items  = malloc(n * sizeof(item));
    unsigned int *current_knapsack = calloc(n, sizeof(unsigned int));
    *max_knapsack = malloc(n * sizeof(unsigned int));
    if (!(items && current_knapsack && *max_knapsack)) {
        free(items);
        free(current_knapsack);
        free(*max_knapsack);
        *max_knapsack = NULL;
        return 0;
    }
    /* Populate the array of items */
    for (i = 0; i < n; i++) {
        items[i].id = i;
        items[i].weight = weights[i];
        items[i].profit = profits[i];
        items[i].profit_density = profits[i] / weights[i];
    }
    /* Sort into decreasing density order */
    qsort(items, n, sizeof(item),
            (int (*)(const void *, const void *))compare_items);
    knapsack_recursive(items, n, capacity, current_knapsack, &current_weight,
            &current_profit, *max_knapsack, &max_profit, 0);
    free(items);
    free(current_knapsack);
    return max_profit;
}

Here is an example program:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    double weights[] = {3, 5, 2, 1};
    double profits[] = {9, 10, 7, 4};
    const size_t n = sizeof(profits) / sizeof(profits[0]);
    const double capacity = 7;
    unsigned int *max_knapsack;
    double max_profit = knapsack(weights, profits, n, capacity, &max_knapsack);
    unsigned int i;
    printf("Profit: %.2f\n", max_profit);
    printf("Knapsack contains:\n");
    for (i = 0; i < n; i++) {
        if (max_knapsack[i] == 1) {
            printf("Item %u with weight %.2f and profit %.2f\n", i, weights[i], profits[i]); 
        }
    }
    free(max_knapsack);
    return 0;
}

The output:

Profit: 20.00
Knapsack contains:
Item 0 with weight 3.00 and profit 9.00
Item 2 with weight 2.00 and profit 7.00
Item 3 with weight 1.00 and profit 4.00

Value-Independent Knapsack Problem using backtracking in C

In another post I described a backtracking algorithm for the Subset-Sum Problem, in which the aim is to find a subset of a set of weights that sums to a given weight. A related problem, which is sometimes called Subset-Sum but is also called Value-Independent Knapsack, is to find a subset of the set of weights that is the maximum weight less than or equal to the given weight, rather than the exact weight.

This problem can be thought of as a 0-1 knapsack problem in which the weights are equal to the values for all items. Like 0-1 knapsack, the problem is NP-hard, but a backtracking algorithm can produce an exact solution quite efficiently. This is a backtracking algorithm for Value Independent Knapsack in C. The function subset_sum() takes an array of weights and its size, a capacity, and an out parameter for the solution array, and returns the weight of the best set found.

static void subset_sum_recursive(const unsigned int *weights, size_t n, unsigned int capacity, 
        unsigned int *current_set, unsigned int *current_weight, unsigned int *max_set, 
        unsigned int *max_weight, unsigned int *remaining_weight, unsigned int level)
{
    if (level == n) {
        /* Found a new best set */
        *max_weight = *current_weight;
        memcpy(max_set, current_set, n * sizeof(unsigned int));
        return;
    }
    *remaining_weight -= weights[level];
    if (*current_weight + weights[level] <= capacity) {
        /* Try solutions that include this item */
        *current_weight += weights[level];
        current_set[level] = 1;
        subset_sum_recursive(weights, n, capacity, current_set, current_weight, 
                max_set, max_weight, remaining_weight, level + 1);
        *current_weight -= weights[level];
        current_set[level] = 0;
    }
    if (*current_weight + *remaining_weight > *max_weight) { 
        /* Still promising */
        subset_sum_recursive(weights, n, capacity, current_set, current_weight, 
                max_set, max_weight, remaining_weight, level + 1);
    }
    *remaining_weight += weights[level];
}

static unsigned int sum(const unsigned int *numbers, size_t len)
{
    unsigned int total = 0;
    unsigned int i;
    for (i = 0; i < len; i++) {
        total += numbers[i];
    }
    return total;
}

static unsigned int subset_sum(const unsigned int *weights, size_t n, unsigned int capacity,
        unsigned int **max_set)
{
    unsigned int current_weight = 0;
    unsigned int max_weight = 0;
    unsigned int remaining_weight = sum(weights, n);
    unsigned int *current_set = calloc(n, sizeof(unsigned int));
    *max_set = malloc(n * sizeof(unsigned int));
    if (current_set == NULL || *max_set == NULL) {
        free(current_set);
        free(*max_set);
        return 0;
    }
    subset_sum_recursive(weights, n, capacity, current_set, &current_weight, *max_set,
           &max_weight, &remaining_weight, 0);
    free(current_set);
    return max_weight;
}

Here is an example program. It prints the maximum weight found and the elements of the set:

int main(void)
{
    unsigned int weights[] = {8, 6, 2, 3};
    const size_t n = sizeof(weights) / sizeof(weights[0]);
    const unsigned int capacity = 12;
    unsigned int *set;
    unsigned int weight = subset_sum(weights, n, capacity, &set);
    unsigned int i;
    printf("%u\n", weight);
    for (i = 0; i < n; i++) {
        if (set[i]) {
            printf("%u ", weights[i]);
        }
    }
    putchar('\n');
    free(set);
    return 0;
}

The output:

11
8 3

Traveling Salesman Problem using backtracking in C

I have previously shown the Cheapest-Link, Nearest-Neigbour, and Repetitive-Nearest Neighbour algorithms for the Traveling Salesman Problem. These are all greedy algorithms that give an approximate result. The Traveling Salesman Problem is NP-complete, so an exact algorithm will have exponential running time unless \(P=NP\). However, we can reduce the search space for the problem by using backtracking.

This is an implementation of TSP using backtracking in C. It searches the permutation space of vertices, fixing the start of each tour at vertex 0. This means that the last edge is always the one that connects the second-last edge to vertex 0, so it is not necessary to find this edge by permutation. The function traveling_salesman() takes a graph in the form of a matrix of distances (adjmat), the number of vertices (order), and the address of a pointer to an array of unsigned integers used as an output parameter (best_tour). It returns the cost of the best tour, and assigns an array containing the vertices of the tour in order to *best_tour.

#include <stdlib.h>
#include <string.h>

static void swap(unsigned int *a, unsigned int *b)
{
    unsigned int temp = *a;
    *a = *b;
    *b = temp;
}

static void traveling_salesman_recursive(const unsigned int **adjmat, unsigned int order, 
        unsigned int *best_tour, unsigned int *best_tour_cost, unsigned int *partial_tour,
        unsigned int *partial_tour_cost, unsigned int level)
{
    if (level == order - 1) {
        /* Add last two edges to complete the tour */
        unsigned int tour_cost = *partial_tour_cost 
                + adjmat[partial_tour[order - 2]][partial_tour[order - 1]]
                + adjmat[partial_tour[order - 1]][0];
        if (*best_tour_cost == 0 || tour_cost < *best_tour_cost) {
            /* Best tour so far */
            memcpy(best_tour, partial_tour, order * sizeof(unsigned int));
            *best_tour_cost = tour_cost;
        }
    }
    else {
        unsigned int i;
        for (i = level; i < order; i++) {
            if (*best_tour_cost == 0
                || *partial_tour_cost + adjmat[partial_tour[level - 1]][partial_tour[i]]
                    < *best_tour_cost)
            {  
                /* Next permutation */
                swap(&partial_tour[level], &partial_tour[i]);
                unsigned int cost = adjmat[partial_tour[level - 1]][partial_tour[level]];
                *partial_tour_cost += cost;
                traveling_salesman_recursive(adjmat, order, best_tour, best_tour_cost,
                        partial_tour, partial_tour_cost, level + 1);
                *partial_tour_cost -= cost;
                swap(&partial_tour[level], &partial_tour[i]);
            }
        }
    }
}

unsigned int traveling_salesman(const unsigned int **adjmat, unsigned int order, 
        unsigned int **best_tour)
{
    unsigned int i;
    unsigned int best_tour_cost = 0;
    unsigned int partial_tour_cost = 0;
    unsigned int *partial_tour = malloc(order * sizeof(unsigned int));
    *best_tour = malloc(order * sizeof(unsigned int));
    if (partial_tour == NULL || *best_tour == NULL) {
        free(partial_tour);
        free(*best_tour);
        *best_tour = NULL;
        return 0;
    }        
    for (i = 0; i < order; i++) {
        partial_tour[i] = i;
    }
    traveling_salesman_recursive(adjmat, order, *best_tour, &best_tour_cost, partial_tour, 
            &partial_tour_cost, 1);
    free(partial_tour);
    return best_tour_cost;
}

Here is an example program:

#include <stdlib.h>
#include <stdio.h>

int main(void)
{
    unsigned int r1[] = {0, 5, 7, 9, 10};
    unsigned int r2[] = {4, 0, 11, 3, 7};
    unsigned int r3[] = {3, 1, 0, 4, 5};
    unsigned int r4[] = {6, 5, 7, 0, 11} ;
    unsigned int r5[] = {13, 2, 8, 3, 0} ;
    const size_t order = 5; /* Vertices */
    const unsigned int *adjmat[] = { r1, r2, r3, r4, r5 };
    unsigned int *best_tour;
    unsigned int cost = traveling_salesman(adjmat, order, &best_tour);
    unsigned int i;
    printf("Best tour cost: %u\n", cost);
    printf("Vertices:\n");
    for (i = 0; i < order; i++) {
        printf("%u ", best_tour[i]);
    }
    putchar('\n');
    printf("Edge weights:\n");
    for (i = 0; i < order - 1; i++) {
        printf("%u ", adjmat[best_tour[i]][best_tour[i + 1]]);
    }
    printf("%u\n", adjmat[best_tour[order - 1]][0]);
    free(best_tour);
    return 0;
}

The output:

Best tour cost: 23
Vertices:
0 2 4 1 3
Edge weights:
7 5 2 3 6

Maximum Clique using backtracking in C

A graph showing a maximum clique

A clique in a graph is a subgraph in which all vertices are connected to each other – a complete subgraph. The Maximum Clique Problem is to find the largest clique of a graph. For example, in the graph shown above the maximum clique size is 3, and the vertices (1, 2, 4) are a maximum clique, as are (0, 1, 4) and (0, 3, 4).

The Maximum Clique Problem is NP-complete, but can be solved efficiently using backtracking. The following is a backtracking implementation in C. The function maximum_clique() takes a graph in adjacency matrix form and its order (the number of vertices), and will return a maximum clique and its size.

#include <stdlib.h>
#include <string.h>

static void maximum_clique_recursive(const unsigned int **adjmat, unsigned int order, 
        unsigned int *current_clique, unsigned int *current_clique_size, unsigned int *max_clique,
        unsigned int *max_clique_size, unsigned int level)
{
    unsigned int i, connected;
    if (level == order) {
        /* Found a new max clique */
        memcpy(max_clique, current_clique, order * sizeof(unsigned int));
        *max_clique_size = *current_clique_size;
        return;
    }
    /* Find out if current vertex is connected to all vertices in current clique */
    connected = 1;
    for (i = 0; i < level && connected; i++) {
        if (current_clique[i] && !adjmat[level][i]) {
            connected = 0;
        }
    }

    if (connected) {
        /* Add this vertex to the clique */
        current_clique[level] = 1;
        (*current_clique_size)++;
        maximum_clique_recursive(adjmat, order, current_clique, current_clique_size, max_clique, 
                max_clique_size, level + 1);
        (*current_clique_size)--;
    }
    if (*current_clique_size + order - level > *max_clique_size) {
        /* Still promising */
        current_clique[level] = 0;
        maximum_clique_recursive(adjmat, order, current_clique, current_clique_size, max_clique, 
                max_clique_size, level + 1);
    }
}

unsigned int maximum_clique(const unsigned int **adjmat, unsigned int order, 
        unsigned int **max_clique)
{
    unsigned int max_clique_size = 0;
    unsigned int current_clique_size = 0;
    unsigned int *current_clique = malloc(order * sizeof(unsigned int));
    *max_clique = malloc(order * sizeof(unsigned int));
    if (current_clique == NULL || *max_clique == NULL) {
        free(current_clique);
        free(max_clique);
        return 0;
    }
    maximum_clique_recursive(adjmat, order, current_clique, &current_clique_size, *max_clique, 
            &max_clique_size, 0);
    free(current_clique);
    return max_clique_size;
}

Here is an example program that finds a maximum clique on the graph shown at the top:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    const unsigned int order = 5; /* Vertices */
    unsigned int r1[] = {0, 1, 0, 1, 1};
    unsigned int r2[] = {1, 0, 1, 0, 1};
    unsigned int r3[] = {0, 1, 0, 0, 1};
    unsigned int r4[] = {1, 0, 0, 0, 1};
    unsigned int r5[] = {1, 1, 1, 1, 0};
    const unsigned int *adjmat[] = {r1, r2, r3, r4, r5};
    unsigned int *max_clique;
    unsigned int max_clique_size = maximum_clique(adjmat, order, &max_clique);
    unsigned int i;
    printf("Max clique size is %u\n", max_clique_size);
    for (i = 0; i < order; i++) {
        if (max_clique[i] == 1) {
            printf("%u ", i);
        }
    }
    putchar('\n');
    free(max_clique);
    return 0;
}

The output:

Max clique size is 3
1 2 4

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

Sudoku using backtracking in C

The title says it all. Here is the code:

#include <stdlib.h>
#include <stdio.h>

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

static unsigned int get_value(const unsigned int *grid, unsigned int row, unsigned int column)
{
    return grid[row * 9 + column];
}

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

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

static void get_box(unsigned int cell, unsigned int *row, unsigned int *column)
{
    get_row_column(cell, row, column);
    *row = (*row / 3) * 3;
    *column = (*column / 3) * 3;
}

static unsigned int unique_in_box(const unsigned int *grid, unsigned int cell)
{
    unsigned int row, column;
    unsigned int top, left;
    unsigned int r, c;
    unsigned int unique = 1;
    get_row_column(cell, &row, &column);
    get_box(cell, &top, &left);
    for (r = top; r < top + 3 && unique; r++) {
        for (c = left; c < left + 3 && unique; c++) {
            if (r != row && c != column) {
                unique = get_value(grid, r, c) != grid[cell];
            }
        }
    }
    return unique;
}

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

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

static void print_grid(const unsigned int *grid)
{
    unsigned int i;
    for (i = 0; i < 81; i++) {
        printf("%d ", grid[i]);
        if (i % 9 == 8) {
            printf("\n");
        }
    }
    printf("\n");
}

static void sudoku_recursive(unsigned int *grid, unsigned int cell,
        unsigned int *succeeded)
{
    if (!get_next_cell(grid, &cell)) {
        *succeeded = 1;
        print_grid(grid);
    }
    else {
        unsigned int i;
        for (i = 1; i <= 9 && !*succeeded; i++) {
            unsigned int temp = grid[cell];
            grid[cell] = i;
            if (promising(grid, cell)) {
                sudoku_recursive(grid, cell + 1, succeeded);
            }
            grid[cell] = temp;
        }
    }
}

void sudoku(unsigned int *grid)
{
    unsigned int cell = 0;
    unsigned int succeeded = 0;
    sudoku_recursive(grid, cell, &succeeded);
}

An example program with the “World’s hardest sudoku“:

#include <stdio.h>

int main(void)
{
    unsigned int grid[] = {
        8, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 3, 6, 0, 0, 0, 0, 0,
        0, 7, 0, 0, 9, 0, 2, 0, 0,
        0, 5, 0, 0, 0, 7, 0, 0, 0,
        0, 0, 0, 0, 4, 5, 7, 0, 0,
        0, 0, 0, 1, 0, 0, 0, 3, 0,
        0, 0, 1, 0, 0, 0, 0, 6, 8,
        0, 0, 8, 5, 0, 0, 0, 1, 0,
        0, 9, 0, 0, 0, 0, 4, 0, 0
    };
    sudoku(grid);
    return 0;
}

The output:

8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2

Spanning trees of a graph in C

A spanning tree of a graph is a subgraph that includes all of the vertices, but only enough edges to connect them. A connected graph will have more than one spanning tree unless the graph is a tree, in which case it has just one spanning tree which is the graph itself. A spanning tree of a graph of order \(v\) will contain \(v – 1\) edges.

In order to list all of the spanning trees of a graph, we could just construct all of the subsets of the edges of size \(v – 1\), and then check if they form a spanning tree, but that wouldn’t be very efficient. A more efficient method is to use backtracking, which is what the algorithm presented here does.

In order to decide whether or not to add an edge to a partially constructed spanning tree, the algorithm checks that the candidate edge:

  1. Has a higher numeric index than its predecessor
  2. Doesn’t have both edges in the same connected component of the tree

The first condition prevents duplicates because the edges are always listed in ascending order. The second one ensures that the tree doesn’t contain too many edges, because an edge is superfluous if both of its endpoints are in the same connected component. In order to check this condition, I used the connected components of a graph algorithm I described previously.

The C code is below. The function spanning_trees() takes a graph in edge list representation, the number of edges and vertices, and a user callback that is called for every spanning tree found.

#include <stdlib.h>

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

typedef void (*treefn)(const edge *, unsigned int);

/* Check if vertices v1 and v2 are in different components in the tree */
static unsigned int different_components(const edge *tree, unsigned int t, unsigned int order,
        unsigned int v1, unsigned int v2)
{
    int *components;
    unsigned int different;
    connected_components(tree, t, order, &components);
    different = components[v1] != components[v2];
    free(components);
    return different;
}

static void spanning_trees_recursive(const edge *edges, unsigned int n, unsigned int order, 
        edge *tree, unsigned int t, int predecessor, treefn fun)
{
    if (t == order - 1) {
        /* Found a tree */
        fun(tree, order - 1);
    }
    else {
        unsigned int e;
        for (e = predecessor + 1; e < n; e++) {
            if (t == 0 /* First edge */
                || different_components(tree, t, order, 
                    edges[e].first, edges[e].second))
            {
                tree[t] = edges[e];   
                spanning_trees_recursive(edges, n, order, tree, t + 1, e, fun);
            }
        }
    }
}

void spanning_trees(const edge *edges, unsigned int n, unsigned int order, treefn fun)
{
    edge *tree;
    tree = malloc((n - 1) * sizeof(edge));
    if (tree == NULL) {
        return;
    }
    spanning_trees_recursive(edges, n, order, tree, 0, -1, fun);
    free(tree);
}

Here is an example that prints all of the spanning trees of the complete graph on 5 vertices:

#include <stdio.h>
#include <stdlib.h>

/* Calculate the nth triangular number T(n) */
unsigned int triangular_number(unsigned int n)
{
    return (n * (n + 1)) / 2;
}

/* Construct a complete graph on v vertices */
edge *complete_graph(unsigned int v)
{
    const unsigned int n = triangular_number(v - 1);
    unsigned int i, j, k;
    edge *edges = malloc(n * sizeof(edge));
    if (edges != NULL) {
        for (i = 0, k = 0; i < v - 1; i++) {
            for (j = i + 1; j < v; j++) {
                edges[k].first = i;
                edges[k].second = j;
                k++;
            }
        }
    }
    return edges;
}

/* Print the edges in a tree */
static void print_tree(const edge *tree, unsigned int n)
{
    unsigned int e;
    for (e = 0; e < n; e++) {
        printf("(%u, %u) ", tree[e].first, tree[e].second);
    }
    putchar('\n');
}


int main(void)
{
    const unsigned int v = 5;
    const unsigned int n = triangular_number(v - 1);
    edge *edges;
    
    edges = complete_graph(v);
    if (edges == NULL) {
        return 1;
    }
    spanning_trees(edges, n, v, print_tree);
    free(edges);

    return 0;
}

Here is the output. There are 125 spanning trees of the complete graph on 5 vertices:

(0, 1) (0, 2) (0, 3) (0, 4) 
(0, 1) (0, 2) (0, 3) (1, 4) 
(0, 1) (0, 2) (0, 3) (2, 4) 
(0, 1) (0, 2) (0, 3) (3, 4) 
(0, 1) (0, 2) (0, 4) (1, 3) 
(0, 1) (0, 2) (0, 4) (2, 3) 
(0, 1) (0, 2) (0, 4) (3, 4) 
(0, 1) (0, 2) (1, 3) (1, 4) 
(0, 1) (0, 2) (1, 3) (2, 4) 
(0, 1) (0, 2) (1, 3) (3, 4) 
(0, 1) (0, 2) (1, 4) (2, 3) 
(0, 1) (0, 2) (1, 4) (3, 4) 
(0, 1) (0, 2) (2, 3) (2, 4) 
(0, 1) (0, 2) (2, 3) (3, 4) 
(0, 1) (0, 2) (2, 4) (3, 4) 
(0, 1) (0, 3) (0, 4) (1, 2) 
(0, 1) (0, 3) (0, 4) (2, 3) 
(0, 1) (0, 3) (0, 4) (2, 4) 
(0, 1) (0, 3) (1, 2) (1, 4) 
(0, 1) (0, 3) (1, 2) (2, 4) 
(0, 1) (0, 3) (1, 2) (3, 4) 
(0, 1) (0, 3) (1, 4) (2, 3) 
(0, 1) (0, 3) (1, 4) (2, 4) 
(0, 1) (0, 3) (2, 3) (2, 4) 
(0, 1) (0, 3) (2, 3) (3, 4) 
(0, 1) (0, 3) (2, 4) (3, 4) 
(0, 1) (0, 4) (1, 2) (1, 3) 
(0, 1) (0, 4) (1, 2) (2, 3) 
(0, 1) (0, 4) (1, 2) (3, 4) 
(0, 1) (0, 4) (1, 3) (2, 3) 
(0, 1) (0, 4) (1, 3) (2, 4) 
(0, 1) (0, 4) (2, 3) (2, 4) 
(0, 1) (0, 4) (2, 3) (3, 4) 
(0, 1) (0, 4) (2, 4) (3, 4) 
(0, 1) (1, 2) (1, 3) (1, 4) 
(0, 1) (1, 2) (1, 3) (2, 4) 
(0, 1) (1, 2) (1, 3) (3, 4) 
(0, 1) (1, 2) (1, 4) (2, 3) 
(0, 1) (1, 2) (1, 4) (3, 4) 
(0, 1) (1, 2) (2, 3) (2, 4) 
(0, 1) (1, 2) (2, 3) (3, 4) 
(0, 1) (1, 2) (2, 4) (3, 4) 
(0, 1) (1, 3) (1, 4) (2, 3) 
(0, 1) (1, 3) (1, 4) (2, 4) 
(0, 1) (1, 3) (2, 3) (2, 4) 
(0, 1) (1, 3) (2, 3) (3, 4) 
(0, 1) (1, 3) (2, 4) (3, 4) 
(0, 1) (1, 4) (2, 3) (2, 4) 
(0, 1) (1, 4) (2, 3) (3, 4) 
(0, 1) (1, 4) (2, 4) (3, 4) 
(0, 2) (0, 3) (0, 4) (1, 2) 
(0, 2) (0, 3) (0, 4) (1, 3) 
(0, 2) (0, 3) (0, 4) (1, 4) 
(0, 2) (0, 3) (1, 2) (1, 4) 
(0, 2) (0, 3) (1, 2) (2, 4) 
(0, 2) (0, 3) (1, 2) (3, 4) 
(0, 2) (0, 3) (1, 3) (1, 4) 
(0, 2) (0, 3) (1, 3) (2, 4) 
(0, 2) (0, 3) (1, 3) (3, 4) 
(0, 2) (0, 3) (1, 4) (2, 4) 
(0, 2) (0, 3) (1, 4) (3, 4) 
(0, 2) (0, 4) (1, 2) (1, 3) 
(0, 2) (0, 4) (1, 2) (2, 3) 
(0, 2) (0, 4) (1, 2) (3, 4) 
(0, 2) (0, 4) (1, 3) (1, 4) 
(0, 2) (0, 4) (1, 3) (2, 3) 
(0, 2) (0, 4) (1, 3) (3, 4) 
(0, 2) (0, 4) (1, 4) (2, 3) 
(0, 2) (0, 4) (1, 4) (3, 4) 
(0, 2) (1, 2) (1, 3) (1, 4) 
(0, 2) (1, 2) (1, 3) (2, 4) 
(0, 2) (1, 2) (1, 3) (3, 4) 
(0, 2) (1, 2) (1, 4) (2, 3) 
(0, 2) (1, 2) (1, 4) (3, 4) 
(0, 2) (1, 2) (2, 3) (2, 4) 
(0, 2) (1, 2) (2, 3) (3, 4) 
(0, 2) (1, 2) (2, 4) (3, 4) 
(0, 2) (1, 3) (1, 4) (2, 3) 
(0, 2) (1, 3) (1, 4) (2, 4) 
(0, 2) (1, 3) (2, 3) (2, 4) 
(0, 2) (1, 3) (2, 3) (3, 4) 
(0, 2) (1, 3) (2, 4) (3, 4) 
(0, 2) (1, 4) (2, 3) (2, 4) 
(0, 2) (1, 4) (2, 3) (3, 4) 
(0, 2) (1, 4) (2, 4) (3, 4) 
(0, 3) (0, 4) (1, 2) (1, 3) 
(0, 3) (0, 4) (1, 2) (1, 4) 
(0, 3) (0, 4) (1, 2) (2, 3) 
(0, 3) (0, 4) (1, 2) (2, 4) 
(0, 3) (0, 4) (1, 3) (2, 3) 
(0, 3) (0, 4) (1, 3) (2, 4) 
(0, 3) (0, 4) (1, 4) (2, 3) 
(0, 3) (0, 4) (1, 4) (2, 4) 
(0, 3) (1, 2) (1, 3) (1, 4) 
(0, 3) (1, 2) (1, 3) (2, 4) 
(0, 3) (1, 2) (1, 3) (3, 4) 
(0, 3) (1, 2) (1, 4) (2, 3) 
(0, 3) (1, 2) (1, 4) (3, 4) 
(0, 3) (1, 2) (2, 3) (2, 4) 
(0, 3) (1, 2) (2, 3) (3, 4) 
(0, 3) (1, 2) (2, 4) (3, 4) 
(0, 3) (1, 3) (1, 4) (2, 3) 
(0, 3) (1, 3) (1, 4) (2, 4) 
(0, 3) (1, 3) (2, 3) (2, 4) 
(0, 3) (1, 3) (2, 3) (3, 4) 
(0, 3) (1, 3) (2, 4) (3, 4) 
(0, 3) (1, 4) (2, 3) (2, 4) 
(0, 3) (1, 4) (2, 3) (3, 4) 
(0, 3) (1, 4) (2, 4) (3, 4) 
(0, 4) (1, 2) (1, 3) (1, 4) 
(0, 4) (1, 2) (1, 3) (2, 4) 
(0, 4) (1, 2) (1, 3) (3, 4) 
(0, 4) (1, 2) (1, 4) (2, 3) 
(0, 4) (1, 2) (1, 4) (3, 4) 
(0, 4) (1, 2) (2, 3) (2, 4) 
(0, 4) (1, 2) (2, 3) (3, 4) 
(0, 4) (1, 2) (2, 4) (3, 4) 
(0, 4) (1, 3) (1, 4) (2, 3) 
(0, 4) (1, 3) (1, 4) (2, 4) 
(0, 4) (1, 3) (2, 3) (2, 4) 
(0, 4) (1, 3) (2, 3) (3, 4) 
(0, 4) (1, 3) (2, 4) (3, 4) 
(0, 4) (1, 4) (2, 3) (2, 4) 
(0, 4) (1, 4) (2, 3) (3, 4) 
(0, 4) (1, 4) (2, 4) (3, 4) 

Euler circuits using backtracking in C

An Euler circuit on a graph is a tour that traverses every edge before returning to its starting point (compare to a Hamiltonian circuit, which visits every vertex). An Euler circuit may visit vertices more than once.

This is a backtracking algorithm to find all Euler circuits of a graph. It takes the graph in the form of an array of edges, and a user-specified callback, which it calls for every circuit found.

In order to extend a partial circuit with a new edge, the algorithm needs to check that the new edge:

  1. Isn’t in the circuit already
  2. Contains the terminal vertex of the partial circuit as one of its endpoints

In order to facilitate (2), the algorithm keeps track of the terminal vertex of the partial circuit.

The first edge of every circuit is fixed at edge 0, and the first terminal vertex is its second vertex. These two normalisation conditions ensure that no duplicate circuits are generated.

#include <stdlib.h>

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

static unsigned int circuit_contains(const unsigned int *circuit, unsigned int c, unsigned int e)
{
    unsigned int i;
    unsigned int contains = 0;
    for (i = 0; i < c && !contains; i++) {
        contains = circuit[i] == e;
    }
    return contains;
}

typedef void (*circuitfn)(const edge *, unsigned int, const unsigned int *);

static void euler_circuits_recursive(const edge *edges, unsigned int n, unsigned int *circuit, 
        unsigned int c, unsigned int tv, circuitfn fun)
{
    if (c == n) {
        /* Found a circuit */
        fun(edges, n, circuit);
    }
    else {
        unsigned int e;
        for (e = 1; e < n; e++) {
            if (!circuit_contains(circuit, c, e) 
                    && (edges[e].first == tv || edges[e].second == tv))
            {
                circuit[ c] = e;   
                euler_circuits_recursive(edges, n, circuit, c + 1,
                       edges[e].first == tv ? edges[e].second : edges[e].first,
                       fun);
            }
        }
    }
}

void euler_circuits(const edge *edges, unsigned int n, circuitfn fun)
{
    unsigned int *circuit;
    circuit = malloc(n * sizeof(unsigned int));
    if (circuit == NULL) {
        return;
    }
    circuit[0] = 0;
    euler_circuits_recursive(edges, n, circuit, 1, edges[0].second, fun);
    free(circuit);
}

Here is an example program that finds all of the Euler circuits on the complete graph of order 5:

#include <stdio.h>
#include <stdlib.h>

/* Calculate the nth triangular number T(n) */
unsigned int triangular_number(unsigned int n)
{
    return (n * (n + 1)) / 2;
}

/* Construct a complete graph on v vertices */
edge *complete_graph(unsigned int v)
{
    const unsigned int n = triangular_number(v - 1);
    unsigned int i, j, k;
    edge *edges = malloc(n * sizeof(edge));
    if (edges != NULL) {
        for (i = 0, k = 0; i < v - 1; i++) {
            for (j = i + 1; j < v; j++) {
                edges[k].first = i;
                edges[k].second = j;
                k++;
            }
        }
    }
    return edges;
}

/* Print the edges in a circuit */
static void print_circuit(const edge *edges, unsigned int n, const unsigned int *circuit)
{
    unsigned int e;
    for (e = 0; e < n; e++) {
        printf("(%u, %u) ", edges[circuit[e]].first, edges[circuit[e]].second);
    }
    putchar('\n');
}

int main(void)
{
    const unsigned int v = 5;
    const unsigned int n = triangular_number(v - 1);
    edge *edges;
    
    edges = complete_graph(v);
    if (edges == NULL) {
        return 1;
    }
    euler_circuits(edges, n, print_circuit);
    free(edges);

    return 0;
}

Here is the output. There are 132 Euler circuits on the complete graph of order 5:

(0, 1) (1, 2) (0, 2) (0, 3) (1, 3) (1, 4) (2, 4) (2, 3) (3, 4) (0, 4) 
(0, 1) (1, 2) (0, 2) (0, 3) (1, 3) (1, 4) (3, 4) (2, 3) (2, 4) (0, 4) 
(0, 1) (1, 2) (0, 2) (0, 3) (2, 3) (2, 4) (1, 4) (1, 3) (3, 4) (0, 4) 
(0, 1) (1, 2) (0, 2) (0, 3) (2, 3) (2, 4) (3, 4) (1, 3) (1, 4) (0, 4) 
(0, 1) (1, 2) (0, 2) (0, 3) (3, 4) (1, 4) (1, 3) (2, 3) (2, 4) (0, 4) 
(0, 1) (1, 2) (0, 2) (0, 3) (3, 4) (2, 4) (2, 3) (1, 3) (1, 4) (0, 4) 
(0, 1) (1, 2) (0, 2) (0, 4) (1, 4) (1, 3) (2, 3) (2, 4) (3, 4) (0, 3) 
(0, 1) (1, 2) (0, 2) (0, 4) (1, 4) (1, 3) (3, 4) (2, 4) (2, 3) (0, 3) 
(0, 1) (1, 2) (0, 2) (0, 4) (2, 4) (2, 3) (1, 3) (1, 4) (3, 4) (0, 3) 
(0, 1) (1, 2) (0, 2) (0, 4) (2, 4) (2, 3) (3, 4) (1, 4) (1, 3) (0, 3) 
(0, 1) (1, 2) (0, 2) (0, 4) (3, 4) (1, 3) (1, 4) (2, 4) (2, 3) (0, 3) 
(0, 1) (1, 2) (0, 2) (0, 4) (3, 4) (2, 3) (2, 4) (1, 4) (1, 3) (0, 3) 
(0, 1) (1, 2) (2, 3) (0, 3) (0, 2) (2, 4) (1, 4) (1, 3) (3, 4) (0, 4) 
(0, 1) (1, 2) (2, 3) (0, 3) (0, 2) (2, 4) (3, 4) (1, 3) (1, 4) (0, 4) 
(0, 1) (1, 2) (2, 3) (0, 3) (0, 4) (1, 4) (1, 3) (3, 4) (2, 4) (0, 2) 
(0, 1) (1, 2) (2, 3) (0, 3) (0, 4) (3, 4) (1, 3) (1, 4) (2, 4) (0, 2) 
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (0, 4) (0, 2) (2, 4) (3, 4) (0, 3) 
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (0, 4) (0, 3) (3, 4) (2, 4) (0, 2) 
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (2, 4) (0, 2) (0, 3) (3, 4) (0, 4) 
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (2, 4) (0, 2) (0, 4) (3, 4) (0, 3) 
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (3, 4) (0, 3) (0, 2) (2, 4) (0, 4) 
(0, 1) (1, 2) (2, 3) (1, 3) (1, 4) (3, 4) (0, 3) (0, 4) (2, 4) (0, 2) 
(0, 1) (1, 2) (2, 3) (3, 4) (0, 4) (0, 2) (2, 4) (1, 4) (1, 3) (0, 3) 
(0, 1) (1, 2) (2, 3) (3, 4) (0, 4) (0, 3) (1, 3) (1, 4) (2, 4) (0, 2) 
(0, 1) (1, 2) (2, 3) (3, 4) (1, 4) (1, 3) (0, 3) (0, 2) (2, 4) (0, 4) 
(0, 1) (1, 2) (2, 3) (3, 4) (1, 4) (1, 3) (0, 3) (0, 4) (2, 4) (0, 2) 
(0, 1) (1, 2) (2, 3) (3, 4) (2, 4) (0, 2) (0, 3) (1, 3) (1, 4) (0, 4) 
(0, 1) (1, 2) (2, 3) (3, 4) (2, 4) (0, 2) (0, 4) (1, 4) (1, 3) (0, 3) 
(0, 1) (1, 2) (2, 4) (0, 4) (0, 2) (2, 3) (1, 3) (1, 4) (3, 4) (0, 3) 
(0, 1) (1, 2) (2, 4) (0, 4) (0, 2) (2, 3) (3, 4) (1, 4) (1, 3) (0, 3) 
(0, 1) (1, 2) (2, 4) (0, 4) (0, 3) (1, 3) (1, 4) (3, 4) (2, 3) (0, 2) 
(0, 1) (1, 2) (2, 4) (0, 4) (0, 3) (3, 4) (1, 4) (1, 3) (2, 3) (0, 2) 
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (0, 3) (0, 2) (2, 3) (3, 4) (0, 4) 
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (0, 3) (0, 4) (3, 4) (2, 3) (0, 2) 
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (2, 3) (0, 2) (0, 3) (3, 4) (0, 4) 
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (2, 3) (0, 2) (0, 4) (3, 4) (0, 3) 
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (3, 4) (0, 4) (0, 2) (2, 3) (0, 3) 
(0, 1) (1, 2) (2, 4) (1, 4) (1, 3) (3, 4) (0, 4) (0, 3) (2, 3) (0, 2) 
(0, 1) (1, 2) (2, 4) (3, 4) (0, 3) (0, 2) (2, 3) (1, 3) (1, 4) (0, 4) 
(0, 1) (1, 2) (2, 4) (3, 4) (0, 3) (0, 4) (1, 4) (1, 3) (2, 3) (0, 2) 
(0, 1) (1, 2) (2, 4) (3, 4) (1, 3) (1, 4) (0, 4) (0, 2) (2, 3) (0, 3) 
(0, 1) (1, 2) (2, 4) (3, 4) (1, 3) (1, 4) (0, 4) (0, 3) (2, 3) (0, 2) 
(0, 1) (1, 2) (2, 4) (3, 4) (2, 3) (0, 2) (0, 3) (1, 3) (1, 4) (0, 4) 
(0, 1) (1, 2) (2, 4) (3, 4) (2, 3) (0, 2) (0, 4) (1, 4) (1, 3) (0, 3) 
(0, 1) (1, 3) (0, 3) (0, 2) (1, 2) (1, 4) (2, 4) (2, 3) (3, 4) (0, 4) 
(0, 1) (1, 3) (0, 3) (0, 2) (1, 2) (1, 4) (3, 4) (2, 3) (2, 4) (0, 4) 
(0, 1) (1, 3) (0, 3) (0, 2) (2, 3) (3, 4) (1, 4) (1, 2) (2, 4) (0, 4) 
(0, 1) (1, 3) (0, 3) (0, 2) (2, 3) (3, 4) (2, 4) (1, 2) (1, 4) (0, 4) 
(0, 1) (1, 3) (0, 3) (0, 2) (2, 4) (1, 4) (1, 2) (2, 3) (3, 4) (0, 4) 
(0, 1) (1, 3) (0, 3) (0, 2) (2, 4) (3, 4) (2, 3) (1, 2) (1, 4) (0, 4) 
(0, 1) (1, 3) (0, 3) (0, 4) (1, 4) (1, 2) (2, 3) (3, 4) (2, 4) (0, 2) 
(0, 1) (1, 3) (0, 3) (0, 4) (1, 4) (1, 2) (2, 4) (3, 4) (2, 3) (0, 2) 
(0, 1) (1, 3) (0, 3) (0, 4) (2, 4) (1, 2) (1, 4) (3, 4) (2, 3) (0, 2) 
(0, 1) (1, 3) (0, 3) (0, 4) (2, 4) (2, 3) (3, 4) (1, 4) (1, 2) (0, 2) 
(0, 1) (1, 3) (0, 3) (0, 4) (3, 4) (2, 3) (1, 2) (1, 4) (2, 4) (0, 2) 
(0, 1) (1, 3) (0, 3) (0, 4) (3, 4) (2, 3) (2, 4) (1, 4) (1, 2) (0, 2) 
(0, 1) (1, 3) (2, 3) (0, 2) (0, 3) (3, 4) (1, 4) (1, 2) (2, 4) (0, 4) 
(0, 1) (1, 3) (2, 3) (0, 2) (0, 3) (3, 4) (2, 4) (1, 2) (1, 4) (0, 4) 
(0, 1) (1, 3) (2, 3) (0, 2) (0, 4) (1, 4) (1, 2) (2, 4) (3, 4) (0, 3) 
(0, 1) (1, 3) (2, 3) (0, 2) (0, 4) (2, 4) (1, 2) (1, 4) (3, 4) (0, 3) 
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (0, 4) (0, 2) (2, 4) (3, 4) (0, 3) 
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (0, 4) (0, 3) (3, 4) (2, 4) (0, 2) 
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (2, 4) (0, 2) (0, 3) (3, 4) (0, 4) 
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (2, 4) (0, 2) (0, 4) (3, 4) (0, 3) 
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (3, 4) (0, 3) (0, 2) (2, 4) (0, 4) 
(0, 1) (1, 3) (2, 3) (1, 2) (1, 4) (3, 4) (0, 3) (0, 4) (2, 4) (0, 2) 
(0, 1) (1, 3) (2, 3) (2, 4) (0, 4) (0, 2) (1, 2) (1, 4) (3, 4) (0, 3) 
(0, 1) (1, 3) (2, 3) (2, 4) (0, 4) (0, 3) (3, 4) (1, 4) (1, 2) (0, 2) 
(0, 1) (1, 3) (2, 3) (2, 4) (1, 4) (1, 2) (0, 2) (0, 3) (3, 4) (0, 4) 
(0, 1) (1, 3) (2, 3) (2, 4) (1, 4) (1, 2) (0, 2) (0, 4) (3, 4) (0, 3) 
(0, 1) (1, 3) (2, 3) (2, 4) (3, 4) (0, 3) (0, 2) (1, 2) (1, 4) (0, 4) 
(0, 1) (1, 3) (2, 3) (2, 4) (3, 4) (0, 3) (0, 4) (1, 4) (1, 2) (0, 2) 
(0, 1) (1, 3) (3, 4) (0, 4) (0, 2) (1, 2) (1, 4) (2, 4) (2, 3) (0, 3) 
(0, 1) (1, 3) (3, 4) (0, 4) (0, 2) (2, 4) (1, 4) (1, 2) (2, 3) (0, 3) 
(0, 1) (1, 3) (3, 4) (0, 4) (0, 3) (2, 3) (1, 2) (1, 4) (2, 4) (0, 2) 
(0, 1) (1, 3) (3, 4) (0, 4) (0, 3) (2, 3) (2, 4) (1, 4) (1, 2) (0, 2) 
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (0, 2) (0, 3) (2, 3) (2, 4) (0, 4) 
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (0, 2) (0, 4) (2, 4) (2, 3) (0, 3) 
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (2, 3) (0, 3) (0, 2) (2, 4) (0, 4) 
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (2, 3) (0, 3) (0, 4) (2, 4) (0, 2) 
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (2, 4) (0, 4) (0, 2) (2, 3) (0, 3) 
(0, 1) (1, 3) (3, 4) (1, 4) (1, 2) (2, 4) (0, 4) (0, 3) (2, 3) (0, 2) 
(0, 1) (1, 3) (3, 4) (2, 4) (0, 2) (0, 3) (2, 3) (1, 2) (1, 4) (0, 4) 
(0, 1) (1, 3) (3, 4) (2, 4) (0, 2) (0, 4) (1, 4) (1, 2) (2, 3) (0, 3) 
(0, 1) (1, 3) (3, 4) (2, 4) (1, 2) (1, 4) (0, 4) (0, 2) (2, 3) (0, 3) 
(0, 1) (1, 3) (3, 4) (2, 4) (1, 2) (1, 4) (0, 4) (0, 3) (2, 3) (0, 2) 
(0, 1) (1, 3) (3, 4) (2, 4) (2, 3) (0, 3) (0, 2) (1, 2) (1, 4) (0, 4) 
(0, 1) (1, 3) (3, 4) (2, 4) (2, 3) (0, 3) (0, 4) (1, 4) (1, 2) (0, 2) 
(0, 1) (1, 4) (0, 4) (0, 2) (1, 2) (1, 3) (2, 3) (2, 4) (3, 4) (0, 3) 
(0, 1) (1, 4) (0, 4) (0, 2) (1, 2) (1, 3) (3, 4) (2, 4) (2, 3) (0, 3) 
(0, 1) (1, 4) (0, 4) (0, 2) (2, 3) (1, 3) (1, 2) (2, 4) (3, 4) (0, 3) 
(0, 1) (1, 4) (0, 4) (0, 2) (2, 3) (3, 4) (2, 4) (1, 2) (1, 3) (0, 3) 
(0, 1) (1, 4) (0, 4) (0, 2) (2, 4) (3, 4) (1, 3) (1, 2) (2, 3) (0, 3) 
(0, 1) (1, 4) (0, 4) (0, 2) (2, 4) (3, 4) (2, 3) (1, 2) (1, 3) (0, 3) 
(0, 1) (1, 4) (0, 4) (0, 3) (1, 3) (1, 2) (2, 3) (3, 4) (2, 4) (0, 2) 
(0, 1) (1, 4) (0, 4) (0, 3) (1, 3) (1, 2) (2, 4) (3, 4) (2, 3) (0, 2) 
(0, 1) (1, 4) (0, 4) (0, 3) (2, 3) (1, 2) (1, 3) (3, 4) (2, 4) (0, 2) 
(0, 1) (1, 4) (0, 4) (0, 3) (2, 3) (2, 4) (3, 4) (1, 3) (1, 2) (0, 2) 
(0, 1) (1, 4) (0, 4) (0, 3) (3, 4) (2, 4) (1, 2) (1, 3) (2, 3) (0, 2) 
(0, 1) (1, 4) (0, 4) (0, 3) (3, 4) (2, 4) (2, 3) (1, 3) (1, 2) (0, 2) 
(0, 1) (1, 4) (2, 4) (0, 2) (0, 3) (1, 3) (1, 2) (2, 3) (3, 4) (0, 4) 
(0, 1) (1, 4) (2, 4) (0, 2) (0, 3) (2, 3) (1, 2) (1, 3) (3, 4) (0, 4) 
(0, 1) (1, 4) (2, 4) (0, 2) (0, 4) (3, 4) (1, 3) (1, 2) (2, 3) (0, 3) 
(0, 1) (1, 4) (2, 4) (0, 2) (0, 4) (3, 4) (2, 3) (1, 2) (1, 3) (0, 3) 
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (0, 3) (0, 2) (2, 3) (3, 4) (0, 4) 
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (0, 3) (0, 4) (3, 4) (2, 3) (0, 2) 
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (2, 3) (0, 2) (0, 3) (3, 4) (0, 4) 
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (2, 3) (0, 2) (0, 4) (3, 4) (0, 3) 
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (3, 4) (0, 4) (0, 2) (2, 3) (0, 3) 
(0, 1) (1, 4) (2, 4) (1, 2) (1, 3) (3, 4) (0, 4) (0, 3) (2, 3) (0, 2) 
(0, 1) (1, 4) (2, 4) (2, 3) (0, 3) (0, 2) (1, 2) (1, 3) (3, 4) (0, 4) 
(0, 1) (1, 4) (2, 4) (2, 3) (0, 3) (0, 4) (3, 4) (1, 3) (1, 2) (0, 2) 
(0, 1) (1, 4) (2, 4) (2, 3) (1, 3) (1, 2) (0, 2) (0, 3) (3, 4) (0, 4) 
(0, 1) (1, 4) (2, 4) (2, 3) (1, 3) (1, 2) (0, 2) (0, 4) (3, 4) (0, 3) 
(0, 1) (1, 4) (2, 4) (2, 3) (3, 4) (0, 4) (0, 2) (1, 2) (1, 3) (0, 3) 
(0, 1) (1, 4) (2, 4) (2, 3) (3, 4) (0, 4) (0, 3) (1, 3) (1, 2) (0, 2) 
(0, 1) (1, 4) (3, 4) (0, 3) (0, 2) (1, 2) (1, 3) (2, 3) (2, 4) (0, 4) 
(0, 1) (1, 4) (3, 4) (0, 3) (0, 2) (2, 3) (1, 3) (1, 2) (2, 4) (0, 4) 
(0, 1) (1, 4) (3, 4) (0, 3) (0, 4) (2, 4) (1, 2) (1, 3) (2, 3) (0, 2) 
(0, 1) (1, 4) (3, 4) (0, 3) (0, 4) (2, 4) (2, 3) (1, 3) (1, 2) (0, 2) 
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (0, 2) (0, 3) (2, 3) (2, 4) (0, 4) 
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (0, 2) (0, 4) (2, 4) (2, 3) (0, 3) 
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (2, 3) (0, 3) (0, 2) (2, 4) (0, 4) 
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (2, 3) (0, 3) (0, 4) (2, 4) (0, 2) 
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (2, 4) (0, 4) (0, 2) (2, 3) (0, 3) 
(0, 1) (1, 4) (3, 4) (1, 3) (1, 2) (2, 4) (0, 4) (0, 3) (2, 3) (0, 2) 
(0, 1) (1, 4) (3, 4) (2, 3) (0, 2) (0, 3) (1, 3) (1, 2) (2, 4) (0, 4) 
(0, 1) (1, 4) (3, 4) (2, 3) (0, 2) (0, 4) (2, 4) (1, 2) (1, 3) (0, 3) 
(0, 1) (1, 4) (3, 4) (2, 3) (1, 2) (1, 3) (0, 3) (0, 2) (2, 4) (0, 4) 
(0, 1) (1, 4) (3, 4) (2, 3) (1, 2) (1, 3) (0, 3) (0, 4) (2, 4) (0, 2) 
(0, 1) (1, 4) (3, 4) (2, 3) (2, 4) (0, 4) (0, 2) (1, 2) (1, 3) (0, 3) 
(0, 1) (1, 4) (3, 4) (2, 3) (2, 4) (0, 4) (0, 3) (1, 3) (1, 2) (0, 2) 

Hamiltonian circuits using backtracking in C

A Hamiltonian circuit of a graph is a tour that visits every vertex once, and ends at its starting vertex. Finding out if a graph has a Hamiltonian circuit is an NP-complete problem.

This is a backtracking algorithm to find all of the Hamiltonian circuits in a graph. The input is an adjacency matrix, and it calls a user-specified callback with an array containing the order of vertices for each Hamiltonian circuit it finds.

The first vertex for all circuits is fixed at 0, and the last vertex is limited to being less than the second vertex. These are normalisation conditions that prevent duplicates that are cyclic permutations or reversals respectively.

#include <stdlib.h>

static unsigned int circuit_contains(const unsigned int *circuit, unsigned int c, unsigned int v)
{
    unsigned int i;
    unsigned int contains = 0;
    for (i = 0; i < c && !contains; i++) {
        contains = circuit[i] == v;
    }
    return contains;
}

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

static void hamiltonian_circuits_recursive(unsigned int **adjmat, size_t n, unsigned int *circuit,
       unsigned int c, circuitfn fun)
{
    if (c == n) {
        /* Found a circuit */
        fun(circuit, n);
    }
    else {
        unsigned int v;
        for (v = 1; v < n; v++) {
            if (!circuit_contains(circuit, c, v) /* Vertex is not in the circuit already */
                && adjmat[circuit[ c - 1]][v] == 1 /* Vertex is adjacent to the previous vertex */
                && (c < n - 1 || (adjmat[0][v] == 1 /* Last vertex is adjacent to the first */
                    && v < circuit[1]))) /* Last vertex is less than the second */
            {
                circuit[ c] = v;
                hamiltonian_circuits_recursive(adjmat, n, circuit, c + 1, fun);
            }
        }
    }
} 

void hamiltonian_circuits(unsigned int **adjmat, size_t n, circuitfn fun)
{
    unsigned int *circuit;
    circuit = malloc(n * sizeof(unsigned int));
    if (circuit == NULL) {
        return;
    }
    circuit[0] = 0;
    hamiltonian_circuits_recursive(adjmat, n, circuit, 1, fun);
    free(circuit);
}

This is an example program that finds all Hamiltonian circuits on the complete graph of order 5. With the constraints on cyclic permutations and direction mentioned above, there are \((n – 1)!/2\) Hamiltonian circuits on a complete graph of order \(n\).

#include <stdio.h>
#include <stdlib.h>

static void print_circuit(const unsigned int *circuit, size_t len)
{
    unsigned int v;
    for (v = 0; v < len; v++) {
        printf("%d ", circuit[v]);
    }
    putchar('\n');
}

int main(void)
{
    unsigned int **adjmat;
    const size_t n = 5;
    unsigned int i, j;

    /* Create a complete graph on 5 vertices */
    adjmat = malloc(n * sizeof(unsigned int *));
    for (i = 0; i < n; i++) {
        adjmat[i] = malloc(n * sizeof(unsigned int));
        for (j = 0; j < n; j++) {
            adjmat[i][j] = 1;
        }
    }

    hamiltonian_circuits(adjmat, n, print_circuit);
    for (i = 0; i < n; i++) {
        free(adjmat[i]);
    }
    free(adjmat);

    return 0;
}

Here is the output. Notice there are \((5 – 1)!/2 = 12\) circuits:

0 2 3 4 1
0 2 4 3 1
0 3 1 4 2
0 3 2 4 1
0 3 4 1 2
0 3 4 2 1
0 4 1 2 3
0 4 1 3 2
0 4 2 1 3
0 4 2 3 1
0 4 3 1 2
0 4 3 2 1

Subset-Sum with backtracking in C

The subset-sum problem is to find a subset of a set of integers that sums to a given value. The decision problem of finding out if such a subset exists is NP-complete. One way of solving the problem is to use backtracking. This is a backtracking solution in C that finds all of the subsets that sum to the target value.

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

static unsigned int promising(int i, size_t len, unsigned int weight, unsigned int total, 
        unsigned int target, const unsigned int *weights)
{
    return (weight + total >= target) && (weight == target || weight + weights[i + 1] <= target);
}

static unsigned int sum(const unsigned int *weights, size_t len)
{
    unsigned int total = 0;
    unsigned int i;
    for (i = 0; i < len; i++) {
        total += weights[i];
    }
    return total;
}

static void subset_sum_recursive(const unsigned int *weights, size_t len, unsigned int target, 
        int i, unsigned int weight, unsigned int total, unsigned int *include, subset_sumfn fun)
{
    if (promising(i, len, weight, total, target, weights)) {
        if (weight == target) {
            fun(include, i + 1);
        }
        else if (i < (int)len - 1){
            include[i + 1] = 1;
            subset_sum_recursive(weights, len, target, i + 1, weight + weights[i + 1], 
                   total - weights[i + 1], include, fun);
            include[i + 1] = 0;
            subset_sum_recursive(weights, len, target, i + 1, weight,
                    total - weights[i + 1], include, fun);
        }
    }
}

void subset_sum(const unsigned int *weights, size_t len, unsigned int target, subset_sumfn fun)
{
    const unsigned int total = sum(weights, len);
    unsigned int *include = calloc(len, sizeof(unsigned int));
    if (include == NULL) {
        return;
    }
    subset_sum_recursive(weights, len, target, -1, 0, total, include, fun);
    free(include);
}

int main(void)
{
    unsigned int weights[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    const unsigned int len = sizeof(weights) / sizeof(unsigned int);
    const unsigned int target = 7;
    subset_sum(weights, len, target, print_vector);
    return 0;
}

The output is in the form of binary strings showing which elements of the original set are in the subset, so for example the first binary string corresponds to 1 + 2 + 4 = 7.

1 1 0 1
1 0 0 0 0 1
0 1 0 0 1
0 0 1 1
0 0 0 0 0 0 1