AC-3 puts back on the queue every arc (XI,, Xi)w henever any value is deleted from the domain of Xi, even if each value of XI, is consistent with several remaining values of Xi.

Suppose that, for every arc (XI,, Xi), we keep track of the number of remaining values of Xi that are consistent with each value of XI,. Explain how to update these numbers efficiently and hence show that arc consistency can be enforced in total time O(n2d2).

5 .11 Show how a single ternary constraint such as "A + B = C" can be turned into three binary constraints by using an auxiliary variable. You may assume finite domains. (Hint:

consider a new variable that takes on values which are pairs of other values, and consider constraints such as "X is the first element of the pair Y.") Next, show how constraints with more than three variables can be treated similarly. Finally, show how unary constraints can be eliminated by altering the domains of variables. This completes the demonstration that any CSP can be transformed into a CSP with only binary constraints.