Backtracking

A subset of Complete Search. This is an intelligent exhaustive search which is worst-case exponential but we find the optimal solution.

Idea

Backtracking uses a decision-tree based philosophy, where in one branch, we make a decision, and in the other binary branch, we do something different

Identification

Use for:

• Constraint satisfaction problems, when you need to build a solution step-by-step and satisfy certain conditions (like SAT).
• Search problems (large solution space but invalid branches can be pruned early)
• Multiple solutions (Explore all possible valid solutions)
• Generate all valid combinations or permutations under constraints

Don’t confuse with Dynamic Programming which can be used to solve problems without overkilling. If there is a single optimal solution, DP might be better.

Has two parts:

• Backtracking
• Pruning the search (when we reach a false on a particular branch)

Backtracking starts with an empty solution and extends the solution step by step.

Steps to Solve

• Define decision space
• Define what a state means
• Decide how to recursively move forward with this choice
• Check if the state is invalid
  • Determine constraints (when do we prune?)
  • If true, backtrack
• Determine goal condition
• Repeat until all possibilities are explored, or a solution is found

A mental model

Each look iteration should start using the same prefix, use a fresh DS per branch and don’t reuse it for siblings

From ChatGPT

Backtracking(path):
    if goal(path):
        record path
        return
    
    # This is choosing what element comes next
    for choice in choices:
        apply(choice)
        if is_valid(path):
            Backtracking(path)
        undo(choice)

^^ Make sure to follow this model rather than the Dynamic Programming take / leave choice model which will lead to a 2^n solution. Doing it this way leads to a wider tree. Anything we skip over in the for loop here is implicitly a “leave” choice.

From ECE406

Start with a problem P₀
Let S = {P₀} be the set of active subproblems
 
while S is non-empty:
    choose a subproblem P ∈ S and remove it from S
    expand it into smaller subproblems P₁, P₂, ..., Pₖ
 
    for each Pᵢ:
        if test(Pᵢ) succeeds:
            halt and return this solution
        if test(Pᵢ) fails:
            discard
        otherwise:
            add Pᵢ to S
 
return that no solution exists

Here, we just need to fill in the choose, expand, and test methods. Don’t make things too complicated, it should be simple. There are many tweaks to improve performance but this is the basic framework.