Introduction
Forward checking looks one step ahead: it removes values that conflict with the variable just assigned. Constraint propagation goes further, and can be done before any assignment at all: if a value cannot work with any value of a neighbour, delete it; that deletion may make other values impossible in turn. Sudoku players do exactly this when they pencil in candidates and cross them out. The standard algorithm for this is AC-3.
How it works
Every binary constraint between X and Y gives two arcs: (X, Y) and (Y, X). The arc (X, Y) is consistent if every value in X's domain has support in Y: some value of Y that satisfies the constraint with it.
Revising (X, Y) removes from X's domain every value without support. For the constraint X < Y with X ∈ {1, 2, 3, 4} and Y ∈ {2, 3}, the values 3 and 4 of X have no larger Y, so X becomes {1, 2}.
AC-3 puts every arc in a queue and repeats:
- take an arc (X, Y) from the queue and revise it;
- if X's domain became empty, the problem has no solution;
- if X's domain changed, put back in the queue every arc (Z, X) with Z ≠ Y, because values of Z may have just lost their support in X.
When the queue is empty, the whole problem is arc consistent.
Arc consistency is a necessary condition for a solution, not a sufficient one. Three variables, each with domain {1, 2}, that must all differ are arc consistent (every value has a different value next to it), yet there is no solution. So AC-3 is usually combined with search: run it first, then again after each assignment during backtracking, which is called maintaining arc consistency (MAC).
Syntax
queue = [(x, y) for every constraint, in both directions]
while queue:
x, y = queue.pop(0)
if revise(x, y): # removed something from x
if not domains[x]: return False # no solution
queue += [(z, x) for z in neighbours(x) if z != y]
return True
Example
domains = {"A": {1, 2, 3, 4}, "B": {1, 2, 3, 4}, "C": {1, 2, 3, 4}}
rules = {
("A", "B"): lambda a, b: a < b,
("B", "C"): lambda b, c: b < c,
("A", "C"): lambda a, c: a + c == 5,
}
arcs = {}
for (x, y), test in rules.items():
arcs[(x, y)] = test
arcs[(y, x)] = lambda value_y, value_x, test=test: test(value_x, value_y)
def revise(x, y):
removed = {vx for vx in domains[x] if not any(arcs[(x, y)](vx, vy) for vy in domains[y])}
domains[x] -= removed
return removed
queue = list(arcs)
while queue:
x, y = queue.pop(0)
removed = revise(x, y)
if removed:
print(f"{x} against {y}: remove {sorted(removed)}, {x} is now {sorted(domains[x])}")
queue.extend((z, w) for (z, w) in arcs if w == x and z != y and (z, w) not in queue)
print("after AC-3:", ", ".join(f"{v} {sorted(d)}" for v, d in domains.items()))
solutions = [
(a, b, c)
for a in sorted(domains["A"])
for b in sorted(domains["B"])
for c in sorted(domains["C"])
if a < b < c and a + c == 5
]
print("solutions (A, B, C):", solutions)Line by line
- Three variables A, B, C range over 1–4 with A < B, B < C and A + C = 5.
- Each constraint becomes two arcs; the second one swaps the arguments of the test.
- AC-3 removes 4 from A (no larger B), 1 from B and 4 from B, and so on; each change puts the affected arcs back in the queue.
- After propagation, A ∈ {1, 2}, B ∈ {2, 3} and C ∈ {3, 4}: much smaller, but not yet a single answer.
- A short search over what is left finds the two real solutions; propagation alone could not tell that A must be 1.
Expected result
A against B: remove [4], A is now [1, 2, 3]
B against A: remove [1], B is now [2, 3, 4]
B against C: remove [4], B is now [2, 3]
C against B: remove [1, 2], C is now [3, 4]
A against C: remove [3], A is now [1, 2]
after AC-3: A [1, 2], B [2, 3], C [3, 4]
solutions (A, B, C): [(1, 2, 4), (1, 3, 4)]
In the real world
Constraint solvers use propagation as their main tool, with specialised algorithms for common constraints such as "all different", which is far stronger than checking pairs. Configuration tools for cars and computers propagate as the customer chooses options, greying out choices that would make the order impossible. Sudoku apps use propagation to generate hints.
Common mistakes
- Revising in only one direction: a constraint gives two arcs.
- Not re-queuing arcs after a domain shrinks, so some values keep support that has disappeared.
- Treating arc consistency as a solution: a search may still be needed.
- Re-queuing (Y, X) after revising (X, Y): Y's values cannot lose support because X's values that were removed had no partner in Y anyway.
Best practices
- Run AC-3 once before search; it often removes a lot cheaply.
- During search, propagate after every assignment and restore domains on backtracking.
- Keep a log of removals while debugging, as the example does.
Summary
A value has support across a constraint if some value of the other variable satisfies it. AC-3 revises arcs from a queue, removing unsupported values and re-checking arcs that point at changed domains, until everything is arc consistent or a domain becomes empty. It prunes search powerfully but does not always solve the problem alone.
Quick check
Key takeaways
- Revising X against Y removes every value of X with no support in Y.
- When a domain shrinks, the arcs pointing at it must be checked again.
- Arc consistency can prove a problem impossible, but it does not always find a solution.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.