Forward Checking

Forward checking is a consistency algorithm that works by propagating constraints from assigned variables to future unassigned variables.

When a variable is assigned, forward checking removes inconsistent values from the domains of future unassigned variables based on current constraints. This prunes the search space.

For example, in a CSP with variables A, B, C and constraint A < B:

• If A is assigned value 3, forward checking would remove all values less than 3 from B’s domain.

• When B is later assigned, forward checking again propagates constraints to future variables like C.

Some key aspects:

• Propagates constraints from past assigned variables
• Prunes domains of future unassigned variables
• Interleaves search and constraint propagation
• Avoids inconsistent assignments early on
• Can detect dead-ends faster before search

Forward checking combines search with lightweight constraint reasoning. It prunes future choices by propagating past assignments quickly. This helps the search algorithm avoid wasteful branches.