# AC-3 algorithm (short for Arc Consistency Algorithm)

I read the AC-3 algorithm. I don't understand some basic thing about it:

In function ac3 (X, D, R1, R2), we call arc-reduce (x, y), and then check if there is a value vy in D(y) which satisfy the constraint. As I understood, even if one of the vx is not satisfy with vy, then arc-reduce return true. And then, we will add to the worklist (z, x) where z!=y, if D(x) is not empty.

What I don't understand is why we do that? We have in D(x) all the values which satisfy with vy. Do why we need to check it also with vz? This is also strange because arc-reduce return false if all vx in D(x) are satsify with vy. So as I understood it, we add the vz constraint to the worklist only when one of the vx is not stasify with vy, but vx is not in the D(x) anymore, so why we do it?

-

(1) Imagine if there is another constraint involving $z$ and some other variable $t$ that has yet to be checked before. Then reducing the domain of $z$ to match the updated domain of $x$ could result in a different arc-reduce $(z, t)$ since the domain of $t$ might be able to cover for the updated domain of $z$, but it may not cover for the un-updated (and actually thus obsolete and incorrect) version of $D(z)$.
(2) Another scenario would be arc-reduce $(t, z)$, and the domain of $z$ might appear to cover more values of $t$, than it would have, had it been properly reduced. This might cause your algorithm to return true, instead of false, if for example, no values of the trimmed $z$ actually fit the $z-t$ constrain anymore.