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 current status of the CSP during the algorithm 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 symmetric constraints, where each arc in the worklist represents a constraint that needs to be checked for consistency. AC-3 proceeds by examining the arcs between pairs of variables. It removes those values from the domain of x which aren't consistent with the constraints between x and y. The algorithm keeps a collection of arcs that are yet to be checked; when the domain of a variable has any values removed, all the arcs of constraints pointing to that pruned variable are added to the collection. Since the domains of the variables are finite and either one arc or at least one value are removed at each step, this algorithm is guaranteed to terminate. For illustration, here is an example of a very simple constraint problem: X has the possible values -- the set of these values are the domain of X, or D. The variable Y has the domain D =. 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. Notice that the actual constraint graph representing this problem must contain two edges between X and Y since C2 is undirected but the graph representation being used by AC-3 is directed. It does so by first removing the non-even values out of the domain of X as required by C1, leaving D =. It then examines the arcs between X and Y implied by C2. Only the pairs,, and match the constraint C2. AC-3 then terminates, with D = and D =. AC-3 is expressed in pseudocode as follows: Input: A set of variables X A set of domains D for each variable x in X. D contains vx0, vx1... vxn, the possible values of x A set of unary constraints R1 on variable x that must be satisfied A set of binary constraints R2 on variables x and y that must be satisfied
Output: Arc consistent domains for each variable.
function ac3 // Initial domains are made consistent with unary constraints. for each x in X D := // 'worklist' contains all arcs we wish to prove consistent or not. worklist :=
do select any arc from worklist worklist := worklist - if arc-reduce if D is empty return failure else worklist := worklist + while worklist not empty
function arc-reduce bool change = false for each vx in D find a value vy in D such that vx and vy satisfy the constraint R2 if there is no such vy return change The algorithm has a worst-case time complexity of O and space complexity of O, where e is the number of arcs and d is the size of the largest domain.
