Backtracking
Algorithms

The paradigm

Backtracking is a systematic method for exploring all potential solutions by building candidates incrementally and abandoning a candidate as soon as it cannot lead to a valid solution.

Core idea

• Build a solution one decision at a time
• At each step, check constraints — if violated, prune this branch
• If a dead end is reached, undo the last decision and try the next option
• If all options exhausted at a level, backtrack further

When to use backtracking

A state space tree is a rooted tree representing all possible states of a backtracking algorithm. Each node is a partial solution; edges represent decisions.

Generic pseudocode

def backtrack(state, decisions):
    if is_solution(state):
        record_solution(state)
        return

    for choice in get_choices(state, decisions):
        if is_valid(state, choice):     # prune
            apply(state, choice)        # choose
            backtrack(state, decisions)  # recurse
            undo(state, choice)         # unchoose

The three pillars

Recursive backtracking uses the call stack to store state. Iterative backtracking uses an explicit stack — identical complexity, avoids stack overflow for very deep searches.

Problem statement

Place N queens on an N x N chessboard so that no two queens attack each other — no shared row, column, or diagonal.

Strategy

• Place queens one row at a time (row 0, 1, ..., N-1)
• For each row, try each column position
• Check constraints: no column conflict, no diagonal conflict
• If no valid column exists, backtrack to the previous row

Solution counts

Constraint checking

def is_safe(board, row, col):
    for prev_row in range(row):
        prev_col = board[prev_row]
        # same column
        if prev_col == col:
            return False
        # same diagonal
        if abs(prev_col - col) == row - prev_row:
            return False
    return True

4-Queens search trace

Row 0: col 0 ✓
  Row 1: col 0 ✗ (column)
  Row 1: col 1 ✗ (diagonal)
  Row 1: col 2 ✓
    Row 2: col 0 ✗ (diagonal)
    Row 2: col 1 ✗ (col conflict row 1)
    Row 2: col 2 ✗ (col conflict row 1)
    Row 2: col 3 ✗ (diagonal)
    ← backtrack to row 1
  Row 1: col 3 ✓
    Row 2: col 0 ✗ (diagonal)
    Row 2: col 1 ✓
      Row 3: col 0 ✗  col 1 ✗  col 2 ✗  col 3 ✗
      ← backtrack
    Row 2: col 2 ✗ ...
    ← backtrack to row 0
Row 0: col 1 ✓
  Row 1: col 3 ✓
    Row 2: col 0 ✓
      Row 3: col 2 ✓  ★ SOLUTION [1,3,0,2]

Efficiency

Problem

Fill a 9x9 grid so every row, column, and 3x3 box contains digits 1–9 exactly once.

Backtracking approach

def solve_sudoku(board):
    cell = find_empty(board)
    if cell is None:
        return True           # solved

    row, col = cell
    for num in range(1, 10):
        if is_valid(board, row, col, num):
            board[row][col] = num
            if solve_sudoku(board):
                return True
            board[row][col] = 0   # undo

    return False  # trigger backtracking

Optimisations

Problem

Given a set S = {s₁, s₂, ..., s_n} and a target T, find all subsets of S that sum to T.

Backtracking solution

def subset_sum(nums, target, start, curr, res):
    if target == 0:
        res.append(curr[:])
        return
    if target < 0:
        return                  # prune: overshot

    for i in range(start, len(nums)):
        curr.append(nums[i])
        subset_sum(nums, target - nums[i],
                   i + 1, curr, res)
        curr.pop()              # backtrack

Pruning strategies

Generate all permutations of [1, 2, ..., n]

def permute(nums, start, result):
    if start == len(nums):
        result.append(nums[:])
        return

    for i in range(start, len(nums)):
        nums[start], nums[i] = nums[i], nums[start]
        permute(nums, start + 1, result)
        nums[start], nums[i] = nums[i], nums[start]

State space

• Level 0: n choices for position 0
• Level 1: n-1 choices for position 1
• Total leaves: n! (all valid — no pruning for plain permutations)

Permutations with constraints

When constraints are added (e.g., "no two adjacent elements differ by more than 2"), pruning becomes effective:

• Check the constraint at each level before recursing
• Invalid placements prune entire subtrees
• Transforms O(n!) into something much smaller in practice

Avoiding duplicates

For inputs with repeated elements (e.g., [1, 1, 2]):

C(n, k): choose k elements from n

def combine(n, k, start, current, result):
    if len(current) == k:
        result.append(current[:])
        return

    # pruning: need (k - len(current)) more
    # only proceed if enough elements remain
    for i in range(start, n-(k-len(current))+2):
        current.append(i)
        combine(n, k, i + 1, current, result)
        current.pop()

Combinations vs permutations

Without pruning: explore all 2ⁿ subsets, filter by size k. With pruning: only generate C(n,k) valid combinations directly.

Problem

Assign colours to vertices of an undirected graph such that no two adjacent vertices share the same colour, using at most k colours.

def graph_colour(graph, k, colours, vertex):
    if vertex == len(graph):
        return True             # all coloured

    for c in range(1, k + 1):
        if is_safe(graph, colours, vertex, c):
            colours[vertex] = c
            if graph_colour(graph, k, colours,
                            vertex + 1):
                return True
            colours[vertex] = 0  # backtrack

    return False

Applications

The minimum k for which a valid colouring exists is the chromatic number X(G). Finding X(G) is NP-hard.

Definitions

def hamiltonian(graph, path, visited):
    if len(path) == len(graph):
        if graph[path[-1]][path[0]]:
            return True   # cycle found
        return False

    for v in range(len(graph)):
        if not visited[v] and graph[path[-1]][v]:
            visited[v] = True
            path.append(v)
            if hamiltonian(graph, path, visited):
                return True
            path.pop()
            visited[v] = False   # backtrack

    return False

Pruning strategies

Formal definition

A CSP is defined by three components:

Examples as CSPs

Constraints: N-Queens — no shared col/diag. Sudoku — row/col/box uniqueness. Graph colouring — adjacent vertices differ. Scheduling — no resource conflicts.

Types of pruning

Implementation guidelines

• Check constraints as early as possible — after each decision, not only at leaf nodes
• Maintain incremental data structures — e.g., boolean arrays for used columns/diagonals in N-Queens
• Sort choices — try the most constrained or promising option first to find solutions (or contradictions) sooner
• Memoisation — cache results of subproblems when the state space has overlapping structure

Bit manipulation

For problems with small state spaces (N-Queens with N ≤ 30), represent sets as bitmasks for O(1) constraint checks.

def solve(row, cols, diag1, diag2, n):
    if row == n:
        return 1
    count = 0
    available = ((1 << n) - 1) \
              & ~(cols | diag1 | diag2)
    while available:
        bit = available & (-available)
        count += solve(row + 1,
                       cols  | bit,
                       (diag1 | bit) << 1,
                       (diag2 | bit) >> 1, n)
        available ^= bit
    return count

Other techniques

Extending backtracking for optimisation

Branch and bound adds a bounding function that estimates the best possible solution achievable from a partial solution.

How it works

• Branch — split the problem into subproblems (like backtracking)
• Bound — compute an optimistic estimate for each subproblem
• Prune — if the bound is worse than the best known solution, discard

Example: 0/1 Knapsack

• Branch — for each item, include or exclude
• Bound — use fractional knapsack (greedy) as upper bound
• Prune — if upper bound ≤ current best profit, skip subtree

Backtracking vs branch and bound

When backtracking does not help

• All solutions are valid (plain enumeration) — no pruning opportunities
• Constraints only checkable at leaf nodes — no early termination
• Highly connected constraint graphs — pruning eliminates few branches

Empirical comparison

Key takeaways

• Backtracking is brute force with pruning — build candidates incrementally, abandon invalid branches early
• The state space tree is the mental model: every node is a decision, pruning removes subtrees
• The generic template — choose, check, recurse, unchoose — applies to N-Queens, Sudoku, graph colouring, and hundreds of other problems
• CSPs unify many backtracking applications under one formal framework
• Variable/value ordering (MRV, LCV) and constraint propagation (AC-3, MAC) dramatically reduce search effort
• Pruning quality is the single biggest performance lever
• Branch and bound extends backtracking to optimisation with bounding functions
• Backtracking does not change the complexity class — but the constant factor is often the difference between seconds and centuries

Recommended reading