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.

- 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.