Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 46 ยท Constraint Satisfaction

Constraint Propagation: Forward Checking and AC-3

Prune CSP domains before and during search: forward checking, arc consistency and the AC-3 algorithm in Python, solving Sudoku, plus path consistency and tree-structured CSPs.

Backtracking has a blind spot: it only discovers that a variable has no legal value when it finally gets around to looking at that variable. By then it may have wasted thousands of assignments. Constraint propagation closes the gap. Instead of waiting for conflicts to appear, the solver uses the constraints to remove impossible values from domains as early as possible, and it repeats that reasoning whenever a domain changes.

This lesson covers three levels of inference, from cheap to thorough: forward checking, arc consistency (the AC-3 algorithm) and a short look at path consistency. You will then use them to solve Sudoku, and finish with a surprising result about CSPs whose constraint graph is a tree.

Forward checking

Forward checking is the simplest look-ahead. Whenever you assign a value to a variable X, look at every unassigned neighbor Y of X and delete from Y's domain any value that conflicts with the new assignment. If some neighbor's domain becomes empty, stop immediately: this branch cannot succeed, and you backtrack without ever visiting that neighbor.

For Sudoku this is intuitive: placing a 5 in a cell deletes 5 from the candidate lists of its 20 neighbors. Forward checking costs very little extra work per assignment, and combined with the MRV rule (which now has accurate domain sizes to work with) it is often enough for easy problems.

Its weakness: it only reasons about the newly assigned variable. It does not notice when removing a value from Y creates a problem for Y's own neighbors.

Arc consistency

The deeper idea is arc consistency. A variable X is arc consistent with a neighbor Y if every value in X's domain has at least one compatible value (a support) in Y's domain. If some value x has no support in Y, then x can never appear in any solution, so we can delete it safely. A CSP is arc consistent when every variable is arc consistent with each of its neighbors.

The operation that enforces one arc is called revise: remove from Domain(X) every value with no support in Domain(Y). The key point is that removing a value from X may cost some other variable Z its support in X, so the arcs pointing into X must be checked again. That is exactly what the AC-3 algorithm does with a queue:

TEXT
AC-3:
    queue = all arcs (X, Y)
    while queue is not empty:
        (X, Y) = queue.pop()
        if revise(X, Y):
            if Domain(X) is empty: return failure
            for each neighbor Z of X other than Y:
                queue.add((Z, X))
    return success
graph LR
    Q["Queue of arcs"] --> R["Take arc (X, Y)<br/>and revise"]
    R -->|"X lost values"| A["Re-add arcs (Z, X)<br/>for neighbors Z"]
    R -->|"Domain of X empty"| F["Failure"]
    R -->|"nothing changed"| Q
    A --> Q

The AC-3 loop. A change in one domain can ripple outward, and the queue keeps track of what still needs checking.

With n variables, domain size d and e constraints, AC-3 runs in O(e d^3) time, which is cheap compared with the exponential search it can save.

AC-3 in action

Take the Australia map with three colours. If we fix WA = red, arc consistency removes red from NT and SA right away. If we also fix Q = green, the effects ripple until a domain becomes empty, which proves there is no solution containing both assignments, without searching at all.

Python AC-3 on the map-colouring problem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the first run, WA = red removes red from NT and SA, and nothing else changes: the problem is still open. In the second run the fixed Q = green forces NT to blue (its neighbors WA and Q take red and green), and then SA, which touches WA, NT and Q, loses blue, green and red in turn. Its domain becomes empty, so AC-3 reports failure before any search starts.

The last example is an important warning. Three mutually adjacent regions cannot be coloured with two colours, yet AC-3 finds nothing to remove: every colour of A has a supporting colour in B, taken one constraint at a time. Arc consistency is sound (it never removes a real solution value) but incomplete (it can miss contradictions that involve three or more variables at once).

Path consistency and stronger forms

To catch failures like the triangle, you need to reason about triples. A pair of variables (X, Z) with values (x, z) is path consistent relative to a third variable Y if some value y works with both. Enforcing this tightens the constraint between X and Z, and it would expose the triangle's contradiction.

More generally, a CSP is k-consistent if any consistent assignment to k - 1 variables can always be extended to a consistent value for any k-th variable. Node consistency is 1-consistency, arc consistency is 2-consistency and path consistency is 3-consistency. Higher levels prune more but cost much more time and memory, so practical solvers use arc consistency during search and add specialised inference for global constraints such as all-different, which has dedicated algorithms far stronger than treating it as many pairwise "not equal" constraints.

Maintaining arc consistency

The most effective use of AC-3 is inside the search. MAC (maintaining arc consistency) runs AC-3 after every assignment, starting the queue with only the arcs (Y, X) into the variable X that was just assigned, because nothing else has changed yet. If AC-3 detects an empty domain, the solver backtracks. MAC does everything forward checking does and more.

Solving Sudoku

Sudoku is the standard showcase. For "not equal" constraints, AC-3 has a particularly simple form: when a cell's domain is a single value, delete that value from all 20 neighbors. The code below builds two puzzles with a fixed seed (a solved grid is shuffled and then cells are blanked), and solves them with three solvers:

  1. Plain backtracking in fixed cell order, no inference.
  2. MRV + forward checking.
  3. MRV + AC-3 (MAC).

It counts the assignments tried (the search effort) and then shows how many cells AC-3 can fill in before any search.

Python Sudoku: plain search versus forward checking versus AC-3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the effort. On the easy puzzle plain backtracking needs 261 assignments while both propagation solvers need exactly 40, one per blank cell, with no wrong guesses at all. On the hard puzzle the gap widens: 2,500 assignments for plain search against 116 for forward checking and 72 for MAC, so maintaining full arc consistency roughly halves the effort again. The last two lines show why. On the easy puzzle AC-3 alone fills in every cell (41 known grows to 81) before any guess is made, so the 40 assignments are only confirmations. On the hard puzzle AC-3 adds nothing at the start (23 known stays 23), so the solver has to guess, but with pruned domains after each guess it guesses very little.

Tip: A common human Sudoku technique called "naked singles" is exactly this propagation rule. Techniques such as "hidden singles" and "naked pairs" correspond to stronger inference for the all-different group constraints.

When the constraint graph is a tree

The structure of the constraint graph can change the complexity class of a problem. General CSPs are NP-hard, but a CSP whose constraint graph is a tree (no cycles) can be solved in time linear in the number of variables:

  1. Pick a root and order the variables so every parent comes before its children.
  2. Working from the leaves up to the root, make each parent arc consistent with its child: delete any parent value that has no support in the child's domain.
  3. Working from the root down to the leaves, assign each variable any value consistent with its already-assigned parent. Step 2 guarantees such a value always exists, so there is never any backtracking.
Python Solving a tree-structured CSP without backtracking

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the first run the upward pass shrinks the domains of C, B and A, and the downward pass then finds a solution on the first try. In the second run restricting F to {1, 2} forces C = 1, which leaves nothing for A (it must be smaller than C), so the algorithm reports no solution without any search.

Real constraint graphs are rarely trees, but the idea generalises: remove a small set of variables (a cutset) so the rest forms a tree, or group variables into a tree of larger sub-problems (tree decomposition). Both make hard-looking problems tractable when the graph is nearly tree-like.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does forward checking do after assigning a value to variable X?

    Forward checking prunes the domains of unassigned neighbors against the new assignment and backtracks immediately if any domain becomes empty.
  2. 2. When is a variable X arc consistent with a neighbor Y?

    Every value of X needs a support in Y. A value without support cannot be part of any solution and can be deleted.
  3. 3. Why does AC-3 re-add arcs (Z, X) to the queue after revising X's domain?

    Removing values from X can leave some value of a neighbor Z without any support, so those arcs must be rechecked.
  4. 4. In the three-region triangle with only two colors, what does AC-3 report?

    Each color has a supporting color on every single arc, so nothing is pruned. Arc consistency is sound but incomplete, so search (or path consistency) is still needed.
  5. 5. How is a tree-structured CSP solved without backtracking?

    After the upward pass every parent value has support in each child, so the downward pass can always extend the assignment. The whole process is linear in the number of variables.

Summary

  • Constraint propagation prunes impossible values from domains instead of waiting for conflicts during search.
  • Forward checking deletes conflicting values from unassigned neighbors after each assignment and fails fast on an empty domain.
  • A value is arc consistent when it has a support in each neighbor; AC-3 enforces this with a queue and re-adds arcs when a domain shrinks.
  • Arc consistency is sound but incomplete: it can miss failures such as the two-colour triangle. Path consistency and k-consistency catch more at a higher cost.
  • MAC (maintaining arc consistency) runs AC-3 after each assignment; with MRV it solved the Sudoku puzzles above with 40 and 72 assignments where plain search needed 261 and 2,500.
  • Tree-structured CSPs are solved in linear time, which motivates cutsets and tree decompositions for nearly tree-like problems.

Next: Games and Minimax.