Fundamental Algorithms8 sections · 291 units
Open in Course

Backtracking Template

The general pattern for backtracking solutions.

Template:

function backtrack(state, choices):
    if state is complete:
        record solution
        return
    for choice in choices:
        if valid:
            make choice
            backtrack(new state, remaining)
            undo choice

Key elements: 1.1. State: partial solution

2.2. Choices: what to add next

3.3. Constraints: which choices valid

4.4. Goal: when complete

"Undo choice" is what makes it backtracking.