Forward checking is a type of constraint propagation used in CSPs. It extends backtracking search with a modest amount of propagation work. It typically doesn’t prune too many states.
During the backtracking search, when assigning a variable , for all constraints that have only one unassigned variable remaining:
- We check all the values of .
- We prune those values that violate .
- And we undo the pruning when we backtrack.
i.e., given a binary constraint , suppose we assign . Then we examine all values of and prune the values of in the search tree that violate the constraint.
For example, take the 4-queens problem, where we begin the check in the image below. We prune and . So this means we must backtrack because there’s no possible assignment for from this partial assignment, called a domain wipe-out for .
Timewise, FC is often about 100 times faster than a naïve backtracking search. With a good heuristic like minimum remaining values, it’s often 10 000 times faster.