directed. It does so by first removing the non-even values out of the domain of X as required by C1, leaving D(X) = { 0, 2, 4 }. It then examines the arcs between X and Y implied by C2. Only the pairs (X=0, Y=4), (X=2, Y=2), and (X=4, Y=0) match the constraint C2. AC-3 then terminates, with D(X) = {0, 2, 4} and D(Y) = {0, 2, 4}. AC-3 is expressed in pseudocode as follows: Input: A set of variables X A set of domains D(x) for each variable x in X. D(x) contains vx0, vx1... vxn, the possible values of x A set of unary constraints R1(x) on variable x that must be satisfied A set of binary constraints R2(x, y) on variables x and y that must be satisfied Output: Arc consistent domains for each variable. function ac3(X, D, R1, R2) // Initial domains are made consistent with unary constraints. for each x in X D(x) := { vx in D(x) | vx satisfies R1(x) } // 'worklist' contains all arcs we wish to prove consistent or not. worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) } do select any arc (x, y) from worklist worklist := worklist - (x, y) if arc-reduce (x, y) if D(x) is empty return failure else worklist := worklist + { (z, x) | z != y and there exists a relation R2(x, z) or a relation R2(z, x) } while worklist not empty function arc-reduce(x, y) bool change = false for each vx in D(x) find a value vy in D(y) such that vx and vy satisfy the constraint R2(x, y) if there is no such vy { D(x) := D(x) - vx change := true } return change The algorithm has a worst-case time complexity of O(ed3) and space complexity of O(e), where e is the number of arcs and d is the size of the largest domain. References A.K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99-118, 1977. Stuart Russell and Peter Norvig. Artificial Intelligence : A Modern Approach, 202-233, 2003. Constraint programming Articles with example pseudocode