AC-3.md

AC-3

AIMA3e

function AC-3(csp) returns false if an inconsistency is found and true otherwise
 inputs: csp, a binary CSP with components (X, D, C)
 local variables: queue, a queue of arcs, initially all the arcs in csp

 while queue is not empty do
   (X_i, X_j) ← REMOVE-FIRST(queue)
   if REVISE(csp, X_i, X_j) then
     if size of D_i = 0 then return false
     for each X_k in X_i.NEIGHBORS − {X_j} do
      add(X_k, X_i) to queue
 return true

---

function REVISE(csp, X_i, X_j) returns true iff we revise the domain of X_i
 revised ← false
 for each x in D_i do
   if no value y in D_j allows (x, y) to satisfy the constraint between X_i and X_j then
    delete x from D_i
    revised ← true
 return revised

---

Figure ?? The arc-consistency algorithm AC-3. After applying AC-3, either every arc is arc-consistent, or some variable has an empty domain, indicating that the CSP cannot be solved. The name "AC-3" was used by the algorithm's inventor (Mackworth, 1977) because it's the third version developed in the paper.