What does forward checking add to a backtracking search beyond validating the current assignment?

## Two directions of looking A backtracking search over a constraint problem assigns variables one at a time. There are two moments where you can spend effort: - **Backward (consistency checking).** After choosing a value, verify it does not conflict with any value already assigned. This is what the occupancy structures in a queen-placement search do, and what most hand-written backtracking does. It guarantees the partial assignment is *currently* valid. - **Forward (look-ahead).** After choosing a value, propagate its consequences into the *unassigned* variables by deleting values that have just become impossible for them. This is what forward checking adds. Backward checking answers "is what I have built so far legal?". Forward checking answers the strictly stronger and much more useful question "can what I have built so far still be completed?" — at least partially, and cheaply. ## The timetabling scenario Model an exam schedule: variables are courses, values are the available time slots, and a hard constraint says two courses with a student in common must not share a slot; a second constraint caps how many exams may run in any one slot, since rooms and invigilators are finite. Plain backtracking schedules courses one by one, checking each new course against those already placed. Suppose an early choice leaves one heavily-overlapping course with no legal slot at all. Plain backtracking has no idea. It keeps scheduling other courses happily, exploring a whole subtree of assignments, and only discovers the contradiction when the recursion finally reaches that doomed course — and then it must unwind, try a different value somewhere shallow, and quite possibly walk into the same wall again from a different direction. This is *thrashing*: repeatedly rediscovering the same contradiction deep in the tree. Forward checking maintains, for each unscheduled course, the set of slots still legal for it. Assigning a slot to a course deletes that slot from the domain of every conflicting unscheduled course, and consumes one unit of that slot's room capacity, deleting the slot from *every* remaining domain once the capacity is used up. The instant a domain becomes empty, the current assignment is refuted and the search backtracks — before descending at all. ## Propagation as the generalization Forward checking propagates one step: from the just-assigned variable to its immediate neighbours. Constraint propagation goes further, re-examining the neighbours of any variable whose domain shrank, cascading until a fixed point. The strongest common form makes every constraint *arc consistent*: for every pair of constrained variables, every value left in one has at least one compatible partner in the other. Deeper propagation catches more contradictions earlier, and costs more per node. There is a genuine dial here, and where you set it is an empirical question about the instance family, not a matter of principle. ## The honest claim about cost This is where candidates most often overstate. Propagation **does not** improve the worst-case complexity class. Constraint satisfaction of this kind is NP-hard; there are instances on which every amount of look-ahead still explodes, and propagation adds per-node work to the exploration you still have to do. What it changes is the practical frontier: for realistic instances, the reduction in nodes explored typically dwarfs the extra work per node, so schedules that plain backtracking cannot finish overnight complete in seconds. The right mental model is a product — **nodes explored multiplied by cost per node** — where propagation trades one factor up to push the other far down. On loosely-constrained instances, where dead ends are rare and shallow, the trade can go the wrong way and plain checking wins. The second, over-corrected wrong answer is "propagation is theatre, it never helps". Also false: on tightly-constrained instances the node reduction is routinely orders of magnitude. ## What maintained domains unlock Once live domains exist, they are free information for ordering decisions. Choosing the unassigned variable with the fewest remaining values — schedule the course that has almost nowhere left to go — makes the search fail fast and high in the tree, where failure is cheap, rather than deep, where it is expensive. Preferring the value that eliminates the fewest options from neighbours pushes in the complementary direction. Neither heuristic is available without look-ahead, which is a large part of why forward checking pays for itself. ## Bookkeeping is the real implementation cost Every deletion must be undone when the assignment that caused it is abandoned, and a value deleted by two different assignments must not be restored by the first undo alone. Implementations therefore record deletions per assignment, or store domains as counters rather than flags. Getting this wrong is silent: the search returns a wrong answer rather than crashing, so a slow reference implementation to cross-check small instances against is worth its weight. ## In the queen-placement setting The direct analogue is to keep, for each row not yet filled, the set of columns still legal for it. Placing a queen deletes its column and the two cells it attacks in each future row; if any future row's set empties, backtrack now instead of descending. The three occupancy structures alone are backward checking; this is the forward version. ## Interview register "Checking is backward-looking — is the partial assignment legal. Forward checking is look-ahead: after each assignment I prune the newly impossible values from the unassigned variables' domains and backtrack the moment one empties, so a contradiction is caught where it is created rather than several levels deeper. Propagation cascades that further. It buys far fewer nodes and enables fail-first ordering, at the price of per-node bookkeeping and undo — and it does not change the worst-case class."