Tree Search by Backtracking

What Is Backtracking?

Backtracking is a systematic algorithm for exploring all possible solutions to a problem by incrementally building candidates and abandoning (pruning) candidates as soon as it is determined they cannot lead to a valid solution.

Backtracking performs a depth-first search on an implicit decision tree, pruning branches that violate constraints.

KEY TAKEAWAY: Backtracking explores the search tree depth-first, abandoning branches early when a partial solution cannot be extended to a valid complete solution. This is more efficient than brute-force but still exponential in the worst case.

General Structure

ALGORITHM Backtrack(candidate, problem)
    if candidate is a complete solution then
        record/output solution
        return
    end if

    for each extension of candidate do
        if extension is valid (doesn't violate constraints) then
            add extension to candidate
            Backtrack(candidate, problem)   // recurse deeper
            remove extension from candidate   // undo (backtrack)
        end if
    end for

The “undo” step is what gives the algorithm its name — it backtracks to the previous state.

Example 1: N-Queens Problem

Place $n$ queens on an $n \times n$ chessboard so no two queens threaten each other.

Constraint: No two queens share the same row, column, or diagonal.

Backtracking strategy:
- Place queens row by row
- For each row, try each column
- If placing a queen creates a conflict, skip (prune)
- If all $n$ queens are placed, record solution

ALGORITHM SolveNQueens(row, placed, n)
    if row = n then
        output placed solution
        return
    end if
    for col ← 0 to n-1 do
        if isValid(placed, row, col) then
            place queen at (row, col)
            SolveNQueens(row + 1, placed, n)
            remove queen from (row, col)   // backtrack
        end if
    end for

Example 2: Graph Colouring

Colour vertices of a graph using at most $k$ colours so no adjacent vertices share a colour.

Backtracking strategy:
- Assign colours to vertices one at a time
- Check constraint: no neighbour has the same colour
- If a conflict arises, backtrack and try the next colour

Example 3: Maze Solving

Find a path from start to goal in a maze.

ALGORITHM SolveMaze(position, visited, goal)
    if position = goal then return [position]
    add position to visited
    for each adjacent cell in maze do
        if cell is not a wall AND not visited then
            path ← SolveMaze(cell, visited, goal)
            if path is not None then
                return [position] + path
            end if
        end if
    end for
    remove position from visited   // backtrack
    return None

Pruning: The Key Optimisation

Pruning eliminates branches that cannot lead to valid solutions, dramatically reducing the search space.

Without pruning: $O(k^n)$ (try all $k$ options at each of $n$ positions)
With aggressive pruning: Can be much faster in practice (though still exponential in worst case)

Applications

Complexity

Backtracking has exponential worst-case complexity — but pruning makes it practical for many real problems that have tight constraints (few valid solutions).

EXAM TIP: In backtracking questions, you may be asked to draw the search tree showing pruned branches. Mark clearly: which branches are pruned and why (which constraint was violated).