Backtracking Search and Constraint Propagation

Unit 4: Optimization and Constraint Satisfaction — Section 4.4

Think of solving a CSP the way you solve a maze. You pick a direction, walk forward, and keep going until you hit a wall. Then you backtrack to the last junction and try a different path. Backtracking search applies this strategy to constraint satisfaction: try one assignment, check whether it violates any constraint, and undo it if it does. Combined with constraint propagation — a technique that predicts consequences of assignments before committing to them — backtracking can solve problems with billions of potential states in milliseconds.

See how constraint propagation and arc consistency work together during backtracking search.

Constraint Propagation

In Section 4.3, you learned to formulate problems as CSPs with variables, domains, and constraints. This section shows how to solve those CSPs systematically.

Why Not Standard DFS?

Ordinary depth-first search would enumerate all possible assignments — for n variables each with domain size d, that is d^n states. For a 9×9 Sudoku with 81 variables and domain {1–9}, this is 9^81 ≈ 2 × 10^77 states. Even if each evaluation took a nanosecond, checking them all would require longer than the age of the universe many times over.

CSPs allow something smarter. Because assignments are commutative — the order doesn’t matter — we can always assign variables one at a time in some fixed order. And because constraint violations can be detected incrementally, we can prune branches as soon as they become impossible.

The Backtracking Algorithm

Backtracking search is a recursive depth-first search that assigns variables one at a time and checks consistency after each assignment. If a contradiction is found, the algorithm backtracks — undoing the most recent assignment — and tries a different value.

Backtracking Search:

  1. If all variables are assigned and all constraints are satisfied, return success

  2. Choose an unassigned variable (call it var)

  3. For each value v in `var’s domain, in some order:

    1. If assigning var = v is consistent with all existing assignments:

      • Tentatively assign var = v

      • Recursively attempt to complete the assignment

      • If the recursive call succeeds, return success

      • Otherwise, undo the assignment (backtrack)

  4. If no value works, return failure (signal the caller to backtrack further)

def backtracking_search(csp):
    return backtrack({}, csp)

def backtrack(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment                         # complete, consistent

    var = select_unassigned_variable(csp, assignment)

    for value in order_domain_values(var, assignment, csp):
        if csp.is_consistent(var, value, assignment):
            assignment[var] = value
            result = backtrack(assignment, csp)
            if result is not None:
                return result
            del assignment[var]                   # backtrack

    return None                                   # failure
Backtracking

A depth-first search strategy for CSPs that assigns one variable at a time, checks constraints after each assignment, and undoes the assignment (backtracks) when a contradiction is detected.

A Traced Example: Map Coloring

To see backtracking in action, apply it to the three-variable problem WA, NT, SA from the Australian map (all must differ from their neighbors):

  1. Assign WA = Red (consistent — no assignments yet)

  2. Assign NT = Red — inconsistent (WA = Red, WA ≠ NT violated)

  3. Assign NT = Green (consistent)

  4. Assign SA = Red — inconsistent (WA = Red, SA ≠ WA violated)

  5. Assign SA = Green — inconsistent (NT = Green, SA ≠ NT violated)

  6. Assign SA = Blue (consistent)

  7. All three assigned, all constraints satisfied — success

Why Backtracking Is Better Than Naive Search:

Naive search would enumerate 3^3 = 27 possible assignments for {WA, NT, SA}. Backtracking checked only 6 partial assignments before finding a solution. The constraint check after each assignment eliminated entire branches of the search tree before they were explored.

For the full 7-variable Australian map, the savings are even larger. For Sudoku (81 variables), the difference is the gap between practical and computationally impossible.

Constraint Propagation: Looking Ahead

Backtracking catches contradictions after they occur — when a newly assigned value conflicts with an existing one. Constraint propagation does something smarter: it uses each new assignment to reduce the domains of unassigned variables, detecting future contradictions before we reach them.

Constraint Propagation

The process of using known variable assignments and constraint relationships to reduce the domains of unassigned variables. If a variable’s domain becomes empty during propagation, a contradiction has been detected and backtracking can occur immediately.

Forward Checking

The simplest form of constraint propagation is forward checking. After assigning a value to variable X, scan every constraint involving X and remove any values from neighboring variables' domains that would violate those constraints.

Forward Checking on Map Coloring:

Assign WA = Red. Forward checking scans WA’s constraints: * WA ≠ NT → remove Red from NT’s domain: {Red, Green, Blue} → {Green, Blue} * WA ≠ SA → remove Red from SA’s domain: {Red, Green, Blue} → {Green, Blue}

Now assign NT = Green. Forward checking scans NT’s constraints: * NT ≠ SA → remove Green from SA’s domain: {Green, Blue} → {Blue} * NT ≠ Q → remove Green from Q’s domain: {Red, Green, Blue} → {Red, Blue}

SA now has only one possible value. If we need to assign SA later, we already know its value must be Blue. Forward checking has done work that backtracking would have done through trial-and-error.

Forward checking is powerful, but it only propagates one step from each assignment. To propagate further, we need arc consistency.

Arc Consistency

Arc consistency is a stronger form of constraint propagation that considers all pairs of variables, not just those directly constrained by the most recent assignment.

Arc Consistency

An arc from variable Xᵢ to variable Xⱼ is arc-consistent if for every value in Xᵢ’s domain, there exists at least one compatible value in Xⱼ’s domain that satisfies the constraint between them. A CSP is arc-consistent if every arc is arc-consistent.

Understanding Arcs

An arc (Xᵢ → Xⱼ) is a directed pair of variables connected by a constraint. It is arc-consistent if every value still in Xᵢ’s domain has at least one "support" — a value in Xⱼ’s domain that satisfies the constraint.

Arc Consistency Check:

Variables X and Y, constraint X ≠ Y. Current domains: D_X = {1, 2, 3}, D_Y = {3}.

Is arc (X → Y) consistent?

  • X = 1: Is there a value in D_Y consistent with X ≠ Y? Y = 3 satisfies 1 ≠ 3. Yes.

  • X = 2: Is there a value in D_Y consistent with X ≠ Y? Y = 3 satisfies 2 ≠ 3. Yes.

  • X = 3: Is there a value in D_Y consistent with X ≠ Y? Y = 3, but 3 ≠ 3 is false. No.

The arc (X → Y) is not consistent. We must remove 3 from D_X. After propagation: D_X = {1, 2}.

This is correct: if Y is forced to be 3, then X can never be 3. Keeping 3 in D_X would be misleading.

The AC-3 Algorithm

AC-3 (Arc Consistency Algorithm #3) is the standard algorithm for enforcing arc consistency across an entire CSP. Developed by Alan Mackworth in 1977, it works by maintaining a queue of arcs to check and re-checking any arc that might have been affected by a domain reduction.

AC-3 Algorithm:

  1. Initialize the queue with all arcs in the CSP

  2. While the queue is not empty:

    1. Remove an arc (Xᵢ, Xⱼ) from the queue

    2. Run REVISE(Xᵢ, Xⱼ): remove from Dᵢ any value with no support in Dⱼ

    3. If any value was removed from Dᵢ:

      • If Dᵢ is now empty, return failure (no solution possible)

      • Add all arcs (Xₖ, Xᵢ) back to the queue — these may now be affected

  3. Return success (all arcs are arc-consistent)

REVISE(Xᵢ, Xⱼ):

For each value x in Dᵢ, check whether there exists any value y in Dⱼ such that the constraint (Xᵢ=x, Xⱼ=y) is satisfied. If not, delete x from Dᵢ and mark the arc as revised.

from collections import deque

def ac3(csp):
    queue = deque(all_arcs(csp))
    while queue:
        xi, xj = queue.popleft()
        if revise(csp, xi, xj):
            if len(csp.domains[xi]) == 0:
                return False          # contradiction
            for xk in csp.neighbors(xi) - {xj}:
                queue.append((xk, xi))
    return True                       # arc-consistent

def revise(csp, xi, xj):
    revised = False
    for x in list(csp.domains[xi]):
        if not any(csp.satisfies(xi, x, xj, y) for y in csp.domains[xj]):
            csp.domains[xi].remove(x)
            revised = True
    return revised
AC-3 (Arc Consistency Algorithm 3)

A polynomial-time algorithm for enforcing arc consistency in a CSP. Time complexity: O(cd³), where c is the number of constraints, d is the maximum domain size, and each arc is added to the queue at most d times. Developed by Alan Mackworth (1977).

AC-3 Complexity

The time complexity of AC-3 is O(cd³):

  • Each arc (Xᵢ, Xⱼ) can be added to the queue at most d times (once each time a value is removed from Dᵢ)

  • There are O(c) arcs

  • Each consistency check for one arc takes O(d²) in the worst case

For typical CSPs, d and c are small, making AC-3 very fast in practice.

What AC-3 Can and Cannot Do

AC-3 is necessary but not sufficient for a solution.

  • What it guarantees: Every value in every domain has at least one compatible partner in neighboring domains.

  • What it does NOT guarantee: A complete consistent assignment exists.

After AC-3, you may have reduced domains significantly — sometimes to single values, effectively solving easy CSPs without search. But on harder problems, domains may still contain multiple values, and search is still required. Arc consistency is the pre-processing step before search, not a replacement for it.

Integrating Backtracking and Constraint Propagation

The two techniques work best together. Maintaining Arc Consistency (MAC) runs AC-3 after every assignment during backtracking search, not just as a one-time preprocessing step.

The Power of Combining AC-3 and Backtracking:

Consider solving a hard Sudoku puzzle:

  • AC-3 preprocessing alone (no search): Reduces many domain sizes and may directly solve cells with only one possibility. Easy puzzles are often solved completely.

  • Backtracking alone (no AC-3): Must explore many branches that end in contradiction only after considerable depth.

  • AC-3 + Backtracking (MAC): After each assignment, AC-3 propagates the consequences throughout the grid. Most contradictions are detected immediately, before additional assignments.

Experimental results on 9×9 Sudoku (hard puzzles):

  • Backtracking alone: thousands of backtracks

  • AC-3 preprocessing + backtracking: hundreds of backtracks

  • MAC (AC-3 after each assignment): tens of backtracks

The integration is straightforward: after each assignment in the backtracking procedure, call AC-3 with only the arcs involving the newly assigned variable. If AC-3 returns failure, backtrack immediately. If it succeeds, proceed with the reduced domains.

Backtracking search provides the completeness that local search lacks: if a solution exists, backtracking will find it. Constraint propagation (AC-3) provides the efficiency: by detecting contradictions early, it eliminates the need to explore vast portions of the search space. Together, they form the foundation of every practical CSP solver — from Sudoku apps to industrial scheduling systems.

Test your understanding of backtracking and arc consistency.

Next: 4.5 Smart Heuristics for CSPs →

Based on the UC Berkeley CS 188 Online Textbook by Nikhil Sharma, Josh Hug, Jacky Liang, and Henry Zhu, licensed under CC BY-SA 4.0.

This work is licensed under CC BY-SA 4.0.