Forward checking

Forward checking is the simplest and most widely used form of constraint propagation. It operates by checking, after each variable assignment, whether the assignment eliminates any values from the domains of unassigned neighboring variables. If a domain becomes empty, the current partial assignment is inconsistent, and the solver backtracks immediately — pruning the entire branch of the search tree before it is explored.

Forward checking is local, greedy, and cheap. It does not re-check constraints after domain reductions that do not result from direct assignments; it does not propagate reductions transitively beyond the immediate neighbors of the assigned variable. This makes it computationally efficient but weak: it can miss inconsistencies that would be detected by stronger forms of propagation like arc consistency or path consistency.

Despite its weakness, forward checking is often the best trade-off in practice. The cost of stronger propagation is not always justified by the search reduction it achieves. In scheduling problems, for example, where constraints are often tight and violations are local, forward checking provides most of the benefit of propagation at a fraction of the cost. The engineering rule of thumb is: use forward checking unless empirical testing shows that stronger propagation pays for itself.

Forward checking is also the conceptual foundation of more advanced techniques. Look-ahead methods are essentially forward checking with additional heuristics: they not only check whether an assignment eliminates values from neighboring domains but estimate the total search cost that would result from making that assignment. The best solvers use a hybrid strategy: forward checking as the baseline propagator, with stronger consistency checking invoked selectively when the solver detects that the search is entering a hard region.