In the CSP lectures, I left the following question unanswered:

Near the end of AC-3, we push all arcs (C,X) onto the queue, but we don't push (Y,X). Why don't we need to push (Y,X)?

There's two cases. First (Y,X) might already be in the queue.

• This is our first pass through all the arcs, when we start working on the constraint problem.
• Some other part of constraint propagation has modified D(X) since the last time we checked (Y,X).

If (Y,X) is already in the queue, then we don't need to add it.

If (Y,X) is not already in the queue, then we've already checked (Y,X) at some point in the past. That check ensured that every value in D(Y) had a matching value in D(X). And, moreover, nothing has happened to D(X) since then, until what we did in the current step of AC-3.

The current step of AC-3 is repairing a problem caused by D(Y) having become smaller. So the situation at the start of our step is that:

• Every value in D(Y) has a matching value in D(X), but
• Some values in D(X) don't have a matching value in D(Y).

Our call to Revise(X,Y) removes that second group of unmatched values. But it doesn't do anything to the first group of values with matches, because the constraint is symmetric. So, after our call to Revise(X,Y), D(X) and D(Y) are now completely consistent with one another.