Arc Consistency
Motivation
In a constraint satisfaction problem, many values in a variable’s domain may be impossible — not because they directly violate a constraint, but because no neighboring variable has a value that would form a valid pair. Arc consistency is the standard local-consistency property that detects and removes these dead-end values, dramatically shrinking the search space before or during backtracking search (Russell and Norvig 2020).
Arc consistency is the canonical example of constraint propagation: deducing forced consequences of the current state without committing to any new assignment.
Problem
Restrict to binary CSPs, where each constraint involves exactly two variables. (Non-binary constraints can always be encoded into binary form, so this is general.) Each pair of constrained variables \((x_i, x_j)\) defines two arcs: \((x_i \to x_j)\) and \((x_j \to x_i)\).
The arc \((x_i \to x_j)\) is arc consistent if, for every value \(v \in D_i\), there exists at least one value \(w \in D_j\) such that the pair \((v, w)\) satisfies the constraint between \(x_i\) and \(x_j\). A CSP is arc consistent if every arc is arc consistent.
The algorithmic task is: given a binary CSP, repeatedly prune values that violate arc consistency until either every arc is consistent (success) or some domain becomes empty (failure — the CSP is unsolvable).
Key Ideas
Pruning arc-inconsistent values is safe
If \((x_i \to x_j)\) is not arc consistent, there is some \(v \in D_i\) with no compatible \(w \in D_j\). Then \(v\) cannot appear in any solution: any assignment with \(x_i = v\) would need to give \(x_j\) some value compatible with \(v\), but no such value exists. We can safely remove \(v\) from \(D_i\) without losing any solutions.
Propagation is necessary
Removing \(v\) from \(D_i\) may in turn break arc consistency on arcs \((x_k \to x_i)\) — some value \(u \in D_k\) may have relied on \(v\) as its compatible partner in \(D_i\). So enforcement must propagate: each domain reduction triggers re-checks on every arc into the affected variable. The propagation continues until no more pruning is possible.
The algorithm is essentially a worklist computation. Each arc is processed at most \(d\) times (once per value that gets removed from its destination domain), so the propagation cascade terminates after \(O(ed)\) work-list pops, where \(e\) is the number of constraints and \(d\) the domain size.
Algorithm
function AC-3(csp):
queue = all arcs (x_i -> x_j) in csp
while queue is not empty:
(x_i, x_j) = queue.pop()
if REVISE(csp, x_i, x_j):
if D_i is empty: return failure
for each x_k that shares a constraint with x_i, k != j:
queue.add((x_k, x_i))
return success
function REVISE(csp, x_i, x_j):
revised = false
for each v in D_i:
if no w in D_j satisfies the (x_i, x_j) constraint with v:
remove v from D_i
revised = true
return revisedWhen REVISE removes a value from \(D_i\), every arc into \(x_i\) (other than from \(x_j\), the arc just processed) is requeued: their consistency may have depended on the removed value.
Walkthrough
Solving a chain by propagation
Three variables \(A, B, C\) with domains \(\{1, 2, 3\}\) each, and constraints \(A < B\) and \(B < C\). AC-3 reduces every domain to a singleton, solving the CSP without any search.
The first revision is \(A \to B\): the value \(A = 3\) has no \(B > 3\) available, so \(3\) is removed from \(D_A\). Symmetrically \(B \to A\) removes \(1\) from \(D_B\). As soon as \(D_B\) shrinks, every arc into \(B\) — here \(C \to B\) — is requeued, and the propagation cascades. By the time the queue empties, each domain is a singleton and the CSP is solved with no search at all. Larger problems are rarely this lucky, but even partial pruning of domains tightens the subsequent backtracking dramatically.
Correctness
Soundness. REVISE removes only values that are arc-inconsistent — no solution can extend such a value to its neighbor, so the pruning loses nothing. By induction over the work-list, the final domains contain every value that could appear in any solution to the original CSP.
Termination. Each REVISE call that removes a value strictly shrinks some domain. Since domains are finite and only shrink, only finitely many REVISE calls can do work. The queue admits at most \(O(ed)\) entries total (each arc requeued once per value removal on its destination), so the algorithm terminates.
Arc consistency does not by itself solve a CSP — it removes provably dead values but may leave a residual problem with no obvious next step, in which case search is still required.
Complexity and Tradeoffs
Let \(n\) be the number of variables, \(d\) the maximum domain size, and \(e\) the number of binary constraints. The total work of AC-3 is \(O(e d^3)\):
- Each arc may be requeued at most \(d\) times — once for each value that gets removed from the variable on its destination side.
- Each REVISE call costs \(O(d^2)\) — for each of \(d\) values, scan up to \(d\) candidate partners.
- \(O(e d) \cdot O(d^2) = O(e d^3)\).
AC-4 reduces this to \(O(e d^2)\) at the cost of more bookkeeping; in practice AC-3 is usually preferred for its simplicity.
When to Use It
| Situation | Approach |
|---|---|
| Preprocess before backtracking search | Run AC-3 once. Cheap, often eliminates large fractions of the domains, sometimes solves the whole problem. |
| Inside backtracking after each assignment | MAC (Maintaining Arc Consistency) — run AC-3 restricted to the affected arcs. Modern default for CSP solvers; strictly stronger than forward checking. |
| Constraints with high arity (3+ variables) | Encode into binary form, or use generalized arc consistency on the original constraints. |
| Stronger consistency needed (e.g., problem stays hard after AC) | Try path consistency or singleton arc consistency — see Variants. |
| Soft constraints / weighted CSPs | AC doesn’t apply directly; use soft-constraint propagation variants. |
Variants
- AC-4. \(O(ed^2)\) in the worst case, using a support-counting data structure instead of re-scanning. More memory, lower asymptotic cost.
- Path consistency. Considers triples of variables: every pair-assignment \((x_i, x_j)\) must extend to a consistent triple with any third variable \(x_k\). Stronger pruning, much higher cost.
- \(k\)-consistency. Every consistent assignment to \(k - 1\) variables extends to any \(k\)th. Enforcing \(n\)-consistency on an \(n\)-variable CSP solves it outright but costs as much as enumeration in the worst case.
- Singleton arc consistency. Asks: would assigning \(x_i = v\) leave the rest arc consistent? Stronger than ordinary AC, sometimes worth the extra cost.
In practice, full \(k\)-consistency for \(k > 2\) is rarely worthwhile; the standard pipeline is AC plus carefully chosen search heuristics.