Arc Consistency -- Brief ☧
Deep version -> | Back to Lattices ->
Q: "Beloved, believe not every spirit, but try the spirits whether
they are of God" (1 John 4:1). In constraint solving, how do we "test"
whether a value in a domain is truly viable -- not just looks possible
but actually is possible?
A: We check whether it has a support. A support means: for this
value, there exists at least one compatible value in every neighboring
variable. A value without support is a false spirit -- it appears possible
in isolation, but if you pick it, you'll hit a dead end because nothing
in the connected variables can work with it.
Q: That's a bit abstract. Can you walk me through a real scenario?
A: Of course. Three servants need to be assigned to three tasks, and
each servant can only do certain tasks:
Martha: {cooking, serving} Mary: {teaching, serving} Lazarus:{cooking} Rule: each servant gets a different task.Now let's "try the spirits." Start with Lazarus -- he can ONLY cook.
That's his one option. So cooking is taken. Now ask: can Martha still
cook? No, because Lazarus must cook. Remove "cooking" from Martha:
Lazarus: {cooking} -- only option, forced -> Remove "cooking" from Martha Martha: {serving} -- only option left, forced -> Remove "serving" from Mary Mary: {teaching} -- only option left, forced All assigned! Arc consistency solved it completely.Each time we removed a value, it was because that value had lost its
support -- there was no consistent way to use it.
Q: You keep saying "arc." What exactly is an arc here?
A: An arc is an edge in the constraint graph -- a line connecting
two variables that share a constraint. Martha and Lazarus share the
"different tasks" constraint, so there's an arc between them.
"Arc consistent" means: for every value in one variable's domain,
there exists at least one compatible value along every arc to a
neighboring variable.
AC-3: The Classic Algorithm
The standard algorithm for enforcing arc consistency is called AC-3.
It works like this:
1. Put all arcs in a queue
2. Pick an arc (A, B)
3. For each value in A's domain:
If no value in B's domain is compatible, remove it from A
4. If A's domain changed, re-queue all arcs involving A
5. Repeat until the queue is empty (fixpoint!)Notice that step 5 is a fixpoint check -- we keep going until
nothing changes. The queue tracks which arcs still need revisiting.
| Property | Value |
|---|---|
| Time complexity | O(ed³) for e arcs, d domain size |
| Space complexity | O(e + nd) |
| Completeness | Necessary but not sufficient (may need search too) |
What should you take away from these complexity numbers? The O(ed³) time
complexity tells us that AC-3 is polynomial -- it will always finish in
reasonable time, even for large problems. The "d³" factor comes from the
three nested operations: for each arc (e), we check each value in one
domain (d), and for each value we scan the other domain for support (d),
and we might need to repeat when domains change (d). On our FPGA, the
inner loop (scanning for support) is replaced by a single AND operation
on bitmask domains, which effectively makes the per-arc cost O(1) instead
of O(d²). This is a massive speedup for large domain sizes.
However, AC-3 is necessary but not sufficient. It prunes many impossible
values cheaply, but sometimes the remaining possibilities still contain
hidden conflicts that only show up when you commit to a specific choice.
That is why real solvers combine arc consistency with backtracking
search -- AC-3 shrinks the search space, and backtracking explores what
remains.
Soli Deo Gloria