Arc Consistency

Arc Consistency: keep pairs of variables consistent, $X\to Y$ is consistent iff for each value of $X$ there are allowed values of $Y$. When checking $X\to Y$, throw out any values of $X$ for which there isn’t an allowed value of $Y$.

In this example, the blue value in NSW is thrown out.

If $X$ loses a value, all pairs $Z\to X$ need to be rechecked. Here we have now run into a situation where we can’t satisfy the problem. So we’ve eliminated the original assignment we’ve chosen.