Past exam of the computer science course of the University of Oxford / 2020 / Artificial intelligence / 2 / b / Solution

Forward checking makes minimum remaining values respond to current restrictions rather than the original constraint domain sizes. After $X=v$, its neighbors may have fewer choices, become forced or lose all choices. Minimum remaining values then selects the newly constrained variable early, while an empty constraint domain triggers immediate failure. The two mechanisms expose failure sooner and reduce wasted backtracking.

Forward checking only tests an unassigned neighbor against the newly assigned value. It need not check whether two still-unassigned variables have mutually supporting values. Arc consistency requires every value at either end of each binary constraint to have support in the other constraint domain, and AC-3 propagates deletions until this condition stabilizes or a constraint domain becomes empty.^[ref]

For example, let $X,Y,Z$ initially have constraint domains $\{1,2\}$ with constraints $X\ne Y$ and $Y\ne Z$. Assigning $X=1$ makes forward checking reduce $D_Y$ to $\{2\}$, but leaves $D_Z=\{1,2\}$. Arc consistency also deletes $2$ from $D_Z$, leaving $\{1\}$. Neither procedure alone decides every general constraint satisfaction problem: a triangle of two-valued inequalities satisfies arc consistency but is unsatisfiable.