Constraint satisfaction

AC-3 (Arc Consistency)

AC-3 cleans up a puzzle by deleting choices that can never work.

Interactive demo coming soon — read the theory below

The idea

AC-3 is a "constraint propagation" method for Constraint Satisfaction Problems (CSPs). Each variable has a domain (its list of possible values) and constraints connect pairs of variables. AC-3 repeatedly checks every directed pair of variables (called an "arc") and removes any value from a variable that has no compatible partner value on the other end. It keeps propagating these removals until nothing more can be pruned, leaving the problem smaller and sometimes fully solved.

How it works

Set up: give every variable its domain (list of allowed values) and list the constraints linking pairs of variables.
Build a queue containing every arc, meaning every directed pair (X, Y) where a constraint connects X and Y (both directions are added).
Take one arc (X, Y) off the queue.
Run REVISE: for each value in X's domain, check whether Y's domain still has at least one value that satisfies the constraint. If not, delete that value from X.
If REVISE deleted anything from X, then any other variable Z constrained with X might now be affected, so add every arc (Z, X) back into the queue.
If X's domain ever becomes empty, stop: the CSP has no solution.
Repeat taking arcs off the queue until it is empty.
When the queue empties, every arc is 'consistent': the domains left are pruned, and if each domain has exactly one value you've solved the CSP directly.

OPEN, CLOSED & the data structures

A domain per variable (a shrinking set of candidate values); a set of binary constraints between variable pairs; and a worklist queue of arcs (directed variable pairs) still to be checked. The queue is the engine: removals push affected neighbor-arcs back onto it.

Pseudocode

function AC3(csp):
    queue <- all arcs (Xi, Xj) in csp    # both directions
    while queue is not empty:
        (Xi, Xj) <- pop(queue)
        if REVISE(csp, Xi, Xj):
            if domain(Xi) is empty:
                return FAILURE            # no solution possible
            for each Xk in neighbors(Xi) except Xj:
                add arc (Xk, Xi) to queue
    return TRUE                           # every arc is consistent

function REVISE(csp, Xi, Xj):
    removed <- false
    for each value x in domain(Xi):
        if no value y in domain(Xj) satisfies constraint(Xi, Xj):
            delete x from domain(Xi)
            removed <- true
    return removed

At a glance

Complete?As a solver, no. AC-3 always terminates and correctly makes the problem arc-consistent, but arc consistency alone does not guarantee a solution. It reliably detects some unsolvable problems (empty domain), and it fully solves easy ones, yet many CSPs stay arc-consistent with several values left. That is why AC-3 is usually paired with search (like backtracking) rather than used alone.

Optimal?Not applicable in the usual sense. AC-3 is a pruning/preprocessing step, not an optimizer: it never invents or ranks solutions, it only removes values that provably cannot be part of any solution. It never deletes a value that could appear in a valid assignment, so it is safe (sound). Finding the actual complete assignment is left to the search it feeds.

TimeO(c * d^3) in the worst case, where c is the number of constraints (arcs) and d is the largest domain size. Each arc can re-enter the queue up to d times, and each REVISE costs O(d^2).

SpaceO(c + n*d): the arc queue holds up to c arcs, plus the domains storing up to d values for each of n variables. Modest overhead beyond the CSP itself.

👍 When to use it

As preprocessing before backtracking search, to shrink domains and slash the search space.
Interleaved during search (as 'maintaining arc consistency', MAC) to prune after each assignment.
For puzzles with binary constraints like Sudoku, map coloring, or scheduling, where many values are obviously impossible.
To quickly detect that a CSP is unsolvable when some domain collapses to empty.
When you want a cheap, sound filter that never removes a valid option.

⚠️ Watch out for

Arc consistency does NOT mean solved: an empty queue can still leave multiple values per variable, so you usually still need search.
Arcs are directed: (X, Y) and (Y, X) are different checks; you must consider both directions.
AC-3 handles binary (two-variable) constraints; constraints over 3+ variables must be reformulated first.
Do not forget to re-add neighbor arcs after a deletion, or propagation stops early and you miss prunings.
An empty domain means failure for the whole CSP, not just that one arc.
It never guesses values; if you expect a full assignment out of AC-3 alone on a hard problem, you'll be disappointed.