AC-3 algorithm

The AC-3 algorithm (short for Arc Consistency Algorithm #3) is one of a series of algorithms used for the solution of constraint satisfaction problems (or CSP's). It was developed by Alan Mackworth.

The algorithm

AC-3 operates on constraints, variables, and the variables' domains. A variable can take any of several discrete values; the set of values for a particular variable is known as its domain. A constraint is a relation that limits or constrains the values a variable may have. The constraint may involve the values of other variables.

The CSP can be viewed as a directed graph, where the nodes are the variables of the problem, with edges or arcs between variables that are related by a constraints. AC-3 proceeds by examining the arcs between pairs of variables (x, y). It removes those values from the domains of x and y which aren't consistent with the constraints between x and y.

For illustration, here is an example of a very simple constraint problem: X (a variable) has the possible values {0, 1, 2, 3, 4, 5} -- the set of these values are the domain of X, or D(X). The variable Y likewise has the domain D(y) = {0, 1, 2, 3, 4, 5}. Together with the constraints C1 = "X must be even" and C2 = "X + Y must equal 4" we have a CSP which AC-3 can solve.

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) := { x in D(x) | R1(x) }   
     // 'worklist' contains all arcs we wish to prove consistent or not.
     worklist := { (x, y) | there exists a relation R2(x,y) } and
                 { (y, x) | there exists a relation R2(x,y) }
 
     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 }
     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 all constraints 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(ed³), 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.