Recursion and backtracking

Introduction

Some problems ask for every possible arrangement, or for one that satisfies a set of rules. Backtracking builds a solution one choice at a time: make a choice, recurse to make the next one, then undo the choice and try the next option. When a partial solution already breaks a rule, it gives up on that branch at once.

Some problems have no shortcut, and the only way is to try the possibilities. Backtracking does that in an organised way, and it never tries a continuation of something already known to be wrong.

How it works

All subsets

#include <stdio.h>

int items[] = {1, 2, 3};
int chosen[3];

void subsets(int i, int n) {
    if (i == n) {
        printf("{");
        for (int k = 0; k < n; k++)
            if (chosen[k]) printf(" %d", items[k]);
        printf(" }\n");
        return;
    }
    chosen[i] = 0;   // leave items[i] out
    subsets(i + 1, n);
    chosen[i] = 1;   // put items[i] in
    subsets(i + 1, n);
}

int main(void) {
    subsets(0, 3);
    return 0;
}

Each item is either in or out: two choices per item, so 2ⁿ subsets. subsets(i) decides item i and calls itself for item i + 1; when every item is decided (i == n), it prints one subset. Watch the call stack: every subset is printed 4 calls deep (i = 0, 1, 2, 3), and chosen changes as calls return.

The n-queens puzzle

Place n queens on an n × n chessboard so that no two share a row, column or diagonal. Put one queen per row; for each row, try every column, and only recurse when the new queen is safe from the earlier ones:

int safe(int r, int c) {           /* col[i] is the queen's column in row i */
    for (int i = 0; i < r; i++)
        if (col[i] == c || col[i] - c == i - r || col[i] - c == r - i)
            return 0;              /* same column or same diagonal */
    return 1;
}

Checking safety early prunes the search: most of the nⁿ ways to place one queen per row are never explored. The 4-queens puzzle has 2 solutions; 8-queens has 92.

Syntax

void solve(int position) {
    if (position == n) { report(); return; }   // every choice has been made
    for (each option) {
        if (allowed) {
            choose(option);
            solve(position + 1);
            undo(option);
        }
    }
}

Example

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void permute(int a[], int k, int n) {
    if (k == n) {
        for (int i = 0; i < n; i++) printf("%d ", a[i]);
        printf("\n");
        return;
    }
    for (int i = k; i < n; i++) {
        swap(&a[k], &a[i]);   // choose a[i] for position k
        permute(a, k + 1, n);
        swap(&a[k], &a[i]);   // undo the choice
    }
}

int main(void) {
    int a[] = {1, 2, 3};
    permute(a, 0, 3);
    return 0;
}

To arrange n items, choose which item goes in position k (any of the remaining ones, by swapping it into place), arrange the rest recursively, then swap back: that second swap is the undo that makes it backtracking. There are n! permutations: 6 for 3 items, 3,628,800 for 10.

Line by line

1. swap exchanges two values through their addresses.
2. permute fixes the items before position k and arranges the rest.
3. When k == n, every position is decided, so the arrangement is printed.
4. The loop tries each remaining item at position k by swapping it there.
5. The recursive call arranges everything after position k.
6. The second swap undoes the choice, so the next pass of the loop starts from the same arrangement.
7. main starts at position 0 with three items, which gives 3! = 6 lines.

Expected result

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2 

In the real world

Solvers for Sudoku, timetables and puzzle games are built on backtracking with strong pruning. The same search is at the core of constraint solvers and the tools that check hardware and software designs.

Common mistakes

• Forgetting to undo a choice, so that later branches start from the wrong state.
• Reporting an answer but not returning from the function.
• Trying backtracking with no pruning on inputs far too large for an exponential method.

Best practices

• Write the three parts in order: choose, recurse, undo.
• Check rules as early as possible, to prune the most.
• Test with n = 1 and with an input that has no solution.

Summary

Backtracking explores every choice by choosing, recursing and undoing, and pruning cuts off branches that cannot work. It costs exponential time, so it suits small inputs or problems with strong rules.

Mark lesson complete