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?