= Solution
\b[<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.<CS 188 constraint filtering notes>[§2.3, forward checking and the directed support test]{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.
Back to article page
