146 Chapter 5.Constraint Satisfaction Problems AC-3 s the CSP.p with reduced do mains while queue is not empty do E-FIRST(queue) MO ()then add ()to queue REMoVE-INCONSISTENT-VALUE(e e for sach in DOMAIN[X:]do if no valuey in DoMAIN[X]allows()to satisfy the constraint between X andX then delete r from DOMAIN[X:];removed-true return removed Figure 5.7 The arc consistency algorithm AC-3.After applying AC-3.either every ard is arc-consistent,or some variable has an empty domain,indicating that the CSP cannot be made arc-c sistent (an thus the C nnot be solved The name“AC-3”was use d by the algorithm's inventor (Mackworth,1977)because it's the third version developed in the paper tency that is not detected by pure forward checking Arc nsistency che eking can be applied eithe e the b ginning of th search proce r as a propa after every (The latter algorithr s som MA stency.in epeatedly unt es remain. This is because ome varial an arc inconsistency,a new ar consistency could arise in arcs pointing to tha variable.The full algorithm for arc consistency,AC-3,uses a queue to keep track of the ares that need to be checked for inconsistency.(See Figure 5 7.)Each arc (Xi,Xi) in turn i removed from the agenda and checked:if any values need to be deleted from the domain Xi,then every arc (Xk,Xi)pointing to Xi must be reinserted I on the queue for checking.The complexity of arc consistency checking can be analyzed as follows:a binary CSP has at most O(n2)arcs;each are (X&,Xi)can be inserted on the agenda only d times,because Xi has at most d values to delete;checking consistency of an arc can be done in O(d2)time;so the total worst-case time is O(n2d).Although this is substantially more expensive than forward checking.the extra cost is usually worthwhile Because CSPs include 3SAT as a special case,we do not expect to find a polynomial- time algorithm that can decide whether a given CSP is consistent.Hence,we deduce that arc consistency does not reveal every possible inconsistency.For example,in Figure 5.1,the par- tial assignment WA=red,NSW=red}is inconsistent,but AC-3 will not find the incon- The AC-4 algorithm,due to Mohr and Henderson(1986),runs in O(n).See Exereise 5.10.146 Chapter 5. Constraint Satisfaction Problems function AC-3(csp) returns the CSP, possibly with reduced domains inputs: csp, a binary CSP with variables {X1, X2, . . . , Xn} local variables: queue, a queue of arcs, initially all the arcs in csp while queue is not empty do (Xi , Xj ) ← REMOVE-FIRST(queue) if REMOVE-INCONSISTENT-VALUES(Xi , Xj ) then for each Xk in NEIGHBORS[Xi] do add (Xk, Xi) to queue function REMOVE-INCONSISTENT-VALUES(Xi , Xj ) returns true iff we remove a value removed ←false for each x in DOMAIN[Xi] do if no value y in DOMAIN[Xj ] allows (x ,y) to satisfy the constraint between Xi and Xj then delete x from DOMAIN[Xi]; removed ←true return removed Figure 5.7 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 made arc-consistent (and thus 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. tency that is not detected by pure forward checking. Arc consistency checking can be applied either as a preprocessing step before the be￾ginning of the search process, or as a propagation step (like forward checking) after every assignment during search. (The latter algorithm is sometimes called MAC, for Maintaining Arc Consistency.) In either case, the process must be applied repeatedly until no more incon￾sistencies remain. This is because, whenever a value is deleted from some variable’s domain to remove an arc inconsistency, a new arc inconsistency could arise in arcs pointing to that variable. The full algorithm for arc consistency, AC-3, uses a queue to keep track of the arcs that need to be checked for inconsistency. (See Figure 5.7.) Each arc (Xi , Xj ) in turn is removed from the agenda and checked; if any values need to be deleted from the domain of Xi , then every arc (Xk, Xi) pointing to Xi must be reinserted on the queue for checking. The complexity of arc consistency checking can be analyzed as follows: a binary CSP has at most O(n 2 ) arcs; each arc (Xk, Xi) can be inserted on the agenda only d times, because Xi has at most d values to delete; checking consistency of an arc can be done in O(d 2 ) time; so the total worst-case time is O(n 2d 3 ). Although this is substantially more expensive than forward checking, the extra cost is usually worthwhile.1 Because CSPs include 3SAT as a special case, we do not expect to find a polynomial￾time algorithm that can decide whether a given CSP is consistent. Hence, we deduce that arc consistency does not reveal every possible inconsistency. For example, in Figure 5.1, the par￾tial assignment {WA = red, NSW = red} is inconsistent, but AC-3 will not find the incon- 1 The AC-4 algorithm, due to Mohr and Henderson (1986), runs in O(n 2 d 2 ). See Exercise 5.10