Consider the following finite-domain constraint satisfaction problem over integer-valued variables. Variables and domains: A, D, E : {1, 2, 3, 4} B : {1, 2, 4} C : {1, 3, 4} Constraints: A != B, A = D, E

1. For each iteration of the algorithm indicate: (a) the pair removed from the queue; (b) the new domains of the variables in the removed pair after the removal of inconsistent values, if any; (c) the new queue after the addition of any new pairs.

2. Report the domain obtained at the end of the algorithm for each variable.

function AC-3(csp) returns false if an inconsistency is found and true otherwise input 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 (Xi, X REMOVE-FIRST(queue) if REVISE(csp, xi, xi) then if size of D 0 then return false for each Xk in Xi.NEIGHBORS do add (XK, Xi) to queue return true function REVISE(csp, Xi, Xi) returns true iff we revise the domain of Xi revised false for each r in D do if no value y in Di allows (r,y)to satisfy the constraint between Xi and X then delete r from Di revised true return revised Figure 6.3 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. function AC-3(csp) returns false if an inconsistency is found and true otherwise input 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 (Xi, X REMOVE-FIRST(queue) if REVISE(csp, xi, xi) then if size of D 0 then return false for each Xk in Xi.NEIGHBORS do add (XK, Xi) to queue return true function REVISE(csp, Xi, Xi) returns true iff we revise the domain of Xi revised false for each r in D do if no value y in Di allows (r,y)to satisfy the constraint between Xi and X then delete r from Di revised true return revised Figure 6.3 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