Forward Checking

The idea

Forward Checking is plain backtracking search with an early-warning system. Every time you assign a value to a variable, you immediately delete any values from the still-unassigned neighbouring variables that now conflict with your choice. If any neighbour is left with no legal values at all, you know this path is doomed, so you backtrack right away instead of blundering deeper. It finds failure sooner and saves wasted work.

How it works

1. Start with every variable unassigned and each variable holding its full domain (its list of allowed values).
2. Pick an unassigned variable and choose a value from its current domain.
3. Look at every unassigned variable connected to it by a constraint (its neighbours).
4. From each neighbour's domain, remove any value that would clash with the value you just assigned.
5. Check the neighbours: if any neighbour's domain is now empty, this assignment cannot work.
6. If a domain went empty, undo the assignment (restore the removed values) and try the next value; if none are left, backtrack to the previous variable.
7. If all domains still have at least one value, move on and assign the next variable.
8. Repeat until every variable is assigned (success) or you run out of options at the very start (no solution).

OPEN, CLOSED & the data structures

A current assignment (which variable has which value so far), and a domain for each variable — the shrinking set of still-legal values. Forward Checking also keeps a record of which values it pruned at each step so it can restore them exactly when it backtracks (the classic recursive/stack structure of backtracking).

Pseudocode

function ForwardChecking(assignment, domains):
    if assignment is complete:
        return assignment                      # every variable has a value

    var = pick an unassigned variable
    for each value in domains[var]:
        assign var = value
        pruned = {}                            # remember what we remove
        empty = false
        for each unassigned neighbour Y of var:
            for each v in domains[Y] that conflicts with value:
                remove v from domains[Y]
                record v in pruned[Y]
            if domains[Y] is empty:
                empty = true                   # a neighbour has no options
        if not empty:
            result = ForwardChecking(assignment, domains)
            if result != failure:
                return result
        restore all values in pruned to their domains   # undo
        unassign var
    return failure                             # no value worked -> backtrack

At a glance