UI logo
CS 440/ECE 448
Margaret Fleck

Constraint Satisfaction Problems
Answer to Exercise

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.

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:

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.