Backtracking

Backtracking explores a decision tree and abandons a partial candidate as soon as it cannot lead to a valid solution.

search(state):
    if state is a complete solution: report it
    for each candidate decision:
        if decision is consistent with state:
            apply decision
            search(state)
            undo decision

Correctness structure

• Every reported leaf satisfies the constraints (soundness).
• Every valid solution corresponds to some branch that is never incorrectly pruned (completeness).
• The finite search tree and progress at every recursive call imply termination.

N-queens

Place one queen per row. Track occupied columns and diagonals so an invalid placement is rejected in constant time. The pruning substantially reduces work, but the worst-case search remains exponential. Backtracking complexity is best described using the branching factor and maximum depth, with tighter bounds when the problem permits them.

Engineering choices

Choose the most constrained variable first, order promising candidates early, and update constraint state incrementally. These heuristics change explored work, not the set of valid solutions.

Exercises

1. Generate all subsets and explain why output size is Θ(2ⁿ).
2. Solve a small graph-coloring instance with pruning.
3. Distinguish backtracking from dynamic programming.