Backtracking · Algorithms (DAA)

Backtracking builds a solution one choice at a time. After each choice it checks whether the partial solution can still lead to a valid answer; if not, it undoes the last choice (backtracks) and tries the next option. It is a depth-first search of the state-space tree with pruning.

Pseudocode

BACKTRACK(partial)
    if partial is a complete solution: report it
    for each choice c that can extend partial
        if c keeps partial valid:        // the pruning test
            add c
            BACKTRACK(partial)
            remove c                     // undo: backtrack

N-Queens

Place N queens on an N × N chessboard so that no two attack each other (same row, column or diagonal). Place one queen per row; for each row, try every column that is safe.

C++

#include <iostream>
#include <vector>
using namespace std;

int n, solutions = 0, nodes = 0;
vector<int> col;                               // col[r] = column of the queen in row r

bool safe(int r, int c) {
    for (int i = 0; i < r; i++)
        if (col[i] == c || abs(col[i] - c) == r - i) return false;   // same column or diagonal
    return true;
}

void place(int r) {
    nodes++;
    if (r == n) {
        if (++solutions == 1) {                 // print the first solution as a board
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) cout << (col[i] == j ? "Q " : ". ");
                cout << endl;
            }
        }
        return;
    }
    for (int c = 0; c < n; c++)
        if (safe(r, c)) { col[r] = c; place(r + 1); }       // choose, explore (undo is implicit)
}

int main() {
    for (n = 4; n <= 8; n += 4) {
        col.assign(n, -1); solutions = 0; nodes = 0;
        place(0);
        cout << n << "-queens: " << solutions << " solutions, " << nodes << " nodes explored" << endl << endl;
    }
    return 0;
}

Output

. Q . . 
. . . Q 
Q . . . 
. . Q . 
4-queens: 2 solutions, 17 nodes explored

Q . . . . . . . 
. . . . Q . . . 
. . . . . . . Q 
. . . . . Q . . 
. . Q . . . . . 
. . . . . . Q . 
. Q . . . . . . 
. . . Q . . . . 
8-queens: 92 solutions, 2057 nodes explored

Try it Yourself

Without pruning there would be 8⁸ ≈ 16.7 million placements for N = 8; backtracking explores about two thousand nodes.

Subset sum

Given positive integers and a target, find subsets that add up exactly to the target. For each number, branch on include or exclude; prune when the sum exceeds the target or the remaining numbers cannot reach it.

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> w = {3, 5, 6, 7};
int target = 15;
vector<int> chosen;

void subsetSum(int i, int sum, int remaining) {
    if (sum == target) {
        cout << "{";
        for (size_t k = 0; k < chosen.size(); k++) cout << (k ? ", " : "") << chosen[k];
        cout << "}" << endl;
        return;
    }
    if (i == (int)w.size() || sum + remaining < target || sum > target) return;   // prune
    chosen.push_back(w[i]);
    subsetSum(i + 1, sum + w[i], remaining - w[i]);          // include w[i]
    chosen.pop_back();
    subsetSum(i + 1, sum, remaining - w[i]);                 // exclude w[i]
}

int main() {
    subsetSum(0, 0, 3 + 5 + 6 + 7);
    return 0;
}

Output

{3, 5, 7}

Try it Yourself

Graph colouring

Colour the vertices with at most m colours so that no two adjacent vertices share a colour. Try colours for each vertex in turn, backtracking on conflicts.

C++

#include <iostream>
#include <vector>
using namespace std;

int V = 5, m = 3;
int adj[5][5] = {{0,1,1,1,0},{1,0,1,0,1},{1,1,0,1,1},{1,0,1,0,1},{0,1,1,1,0}};
vector<int> colour(5, 0);

bool ok(int v, int c) {
    for (int u = 0; u < V; u++) if (adj[v][u] && colour[u] == c) return false;
    return true;
}

bool solve(int v) {
    if (v == V) return true;
    for (int c = 1; c <= m; c++)
        if (ok(v, c)) {
            colour[v] = c;
            if (solve(v + 1)) return true;
            colour[v] = 0;                     // backtrack
        }
    return false;
}

int main() {
    const char *names[] = {"red", "green", "blue"};
    if (solve(0)) for (int v = 0; v < V; v++) cout << "vertex " << v << ": " << names[colour[v] - 1] << endl;
    else cout << "not colourable with " << m << " colours" << endl;
    return 0;
}

Output

vertex 0: red
vertex 1: green
vertex 2: blue
vertex 3: green
vertex 4: red

Try it Yourself

The smallest m that works is the graph's chromatic number. Deciding whether a graph is 3-colourable is NP-complete.

Hamiltonian cycle

A Hamiltonian cycle visits every vertex exactly once and returns to the start. Backtracking extends a path one unvisited neighbour at a time and backtracks at dead ends. No polynomial algorithm is known; it is NP-complete.

Problem	Choice at each level	Pruning test
N-Queens	column for the next row	no attack
Subset sum	include / exclude next number	sum too big, or cannot reach target
Graph colouring	colour for the next vertex	no neighbour has that colour
Hamiltonian cycle	next vertex on the path	adjacent and unvisited
Sudoku	digit for the next empty cell	row, column and box rules

Test yourself

4 questions · pick an answer to check it instantly

1
What does backtracking do when a partial solution cannot lead to a valid answer?
2
How many solutions does the 4-Queens problem have?
3
Which subsets of {3, 5, 6, 7} sum to 15?
4
Backtracking explores the state-space tree in which order?

#N-Queens

#Subset sum

#Graph colouring

#Hamiltonian cycle

Test yourself

N-Queens

Subset sum

Graph colouring

Hamiltonian cycle