Forward Checking for CSPs

The CSP lookahead strategy that prunes after every assignment — trace the exact order examiners expect

The Simplest Explanation

A CSP has variables, domains, and constraints. Forward Checking (FC) after each assignment:

  • Remove values from unassigned neighbors that conflict with the new assignment
  • If any domain empties → backtrack immediately (don't wait to assign it)
Remember This

FC = assign one variable → prune neighbors' domains → if empty, backtrack. Process variables and values in alphabetical order (exam convention).

Constraint Graph Example (from 22T3 Papers)

When no edge exists, assume universal relation (all tuples allowed).

Algorithm Trace Pattern

FC begins with X1 = a. What are the next four values assigned (in order)?

StepVariable (alphabetical)Domain after pruningAssigned
1X1—a
2X2pruned by X1=a → remaining e,...e
3X3...2
4X4...5
...X5...p

Exams ask two things:

  1. Next N assignments in order (not just which variables)
  2. First solution found (full assignment when no domain empties)

22T3 AN Example

  • Variables X1-X5, alphabet order, start X1=a
  • Next four values: e,2,5,p (Answer: a,e,2,5,p is first solution)
  • Each step FC prunes incompatible values from all future variables' domains

22T3 FN Example (different graph)

  • Graph: X1-X2, X2-X5, X5-X3, X3-X4, X4-X1 (5-cycle)
  • Next four after X1=a: d,1,2,3 → first solution a,d,3,4,q

FC vs Plain Backtracking

Plain BacktrackingForward Checking
PrunesOnly at assignment timeImmediately forward to neighbors
Fails early?No — detects failure at next variableYes — empty domain detected instantly
Cost per nodeCheapHigher (domain filtering)
Search treeLargerSmaller (prunes earlier)
QuizAfter assigning X1=a, Forward Checking...
QuizExam convention for Forward Checking order is...