Backtracking Search for CSPs

Overview

Backtracking search is the standard complete algorithm for CSPs. Unlike generic DFS, it exploits the commutativity of CSP assignments (order doesn’t matter) and uses domain-specific heuristics to dramatically reduce the search space.

Key insight: We only need to consider assignments to one variable at a time, and a partial assignment that violates a constraint can be abandoned immediately — no need to explore the subtree.

The BACKTRACKING-SEARCH Algorithm

function BACKTRACKING-SEARCH(csp) returns solution or failure
    return BACKTRACK({}, csp)

function BACKTRACK(assignment, csp) returns solution or failure
    if assignment is complete then return assignment
    var ← SELECT-UNASSIGNED-VARIABLE(csp, assignment)
    for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
        if value is consistent with assignment then
            add {var = value} to assignment
            inferences ← INFERENCE(csp, var, assignment)
            if inferences ≠ failure then
                add inferences to csp
                result ← BACKTRACK(assignment, csp)
                if result ≠ failure then return result
            remove {var = value} and inferences from assignment and csp
    return failure

Three pluggable components: - SELECT-UNASSIGNED-VARIABLE — which variable to assign next - ORDER-DOMAIN-VALUES — in what order to try values - INFERENCE — how much propagation to do after each assignment

Variable Ordering: MRV and Degree Heuristic

MRV (Minimum Remaining Values) — “Fail-First”

Choose the variable with the fewest legal values remaining in its domain.

Why it works: Assigns the most constrained variable first, detecting failures earlier. Reduces the branching factor where it matters most.

Example: In map coloring, if SA has only 1 value left and WA has 3, assign SA first.

Degree Heuristic — Tie-Breaker

When multiple variables are tied on MRV, choose the one involved in the most constraints on remaining unassigned variables.

Why: High-degree variables are most likely to create conflicts, so assigning them early catches more failures sooner.

Value Ordering: LCV (Least Constraining Value) — “Succeed-First”

Given a chosen variable, try the value that eliminates the fewest choices from neighboring variables’ domains.

Order values by: Σ_{Xⱼ neighbor of Xᵢ} |{y ∈ Dⱼ : y inconsistent with v}|
(ascending — least constraining first)

Why: We want to find a solution, so try values that leave maximum flexibility for remaining variables. If a value rules out many neighbors’ options, it’s likely a dead end.

Contrast with MRV: MRV is fail-first (for variable choice), LCV is succeed-first (for value choice). Both are greedy but complementary.

Inference: Forward Checking and MAC

After assigning Xᵢ = v:

Forward Checking

For each unassigned variable Xⱼ that shares a constraint with Xᵢ: - Remove from Dⱼ any value inconsistent with v. - If Dⱼ becomes empty → backtrack immediately.

Cost: O(d) per neighbor.

MAC (Maintaining Arc Consistency)

Run AC-3 starting from arcs {(Xⱼ, Xᵢ) : Xⱼ unassigned neighbor of Xᵢ}. Propagates failures further than forward checking.

MAC is the default in modern CSP solvers — the extra propagation cost is worth the reduction in search tree size.

Backtracking Variants

Chronological Backtracking

Standard: when a conflict is detected, undo the most recent assignment and try the next value. Simple but can thrash — if the conflict is caused by a variable assigned 20 steps ago, we keep undoing recent unrelated choices.

Backjumping

When a dead end is reached at variable Xⱼ, jump back to the deepest variable Xᵢ in the conflict set — the set of past variables that directly caused the failure.

Conflict set: variables that are (a) assigned before Xⱼ and (b) constrained with Xⱼ.

Supersedes chronological backtracking with no overhead in terms of nodes visited.

Conflict-Directed Backjumping (CBJ)

When backjumping to Xᵢ, merge the conflict sets: the conflict set at Xᵢ gets augmented with Xⱼ’s conflict set (minus Xᵢ itself). This propagates failure explanations upward.

More powerful than simple backjumping; avoids repeatedly rediscovering the same failures.

Constraint Learning / No-Good Recording

Record the no-good: the partial assignment that led to the failure. Add it as a new constraint. Future search will prune any branch that contains this no-good.

Expensive in memory but can yield exponential speedups on structured problems.

Worked Example: 4-Queens

Variables: Q1, Q2, Q3, Q4 (column of queen in row i) Domains: {1, 2, 3, 4}

Step 1: MRV → all tied → choose Q1. LCV → try Q1=1.
  Forward checking: removes values from Q2, Q3, Q4.

Step 2: MRV → Q2 has fewest. Try Q2=3 (LCV).
  Forward checking removes more values.

Step 3: Q3 domain empty → forward checking detected failure.
  Backtrack to Q2. Try Q2=4.
  ...

Continue until Q1=2, Q2=4, Q3=1, Q4=3 found.

Theoretical Properties

In practice: MRV + degree + LCV + MAC reduces effective branching dramatically. Many structured CSPs (Sudoku, scheduling) are solved in milliseconds.