Constraint Satisfaction - Learning Module

Loading content...

0/276

Forward Checking (Conceptual)

Looking One Step Ahead

Imagine playing chess and only checking if your move puts your king in check after you've made it. You'd waste enormous time making losing moves and then taking them back. A better strategy: before committing to a move, check whether it leaves you in an inescapable position.

This is precisely what forward checking does for constraint satisfaction. Instead of blindly making assignments and waiting to discover constraint violations, forward checking looks ahead after each assignment to eliminate values that have become impossible. If any variable's domain becomes empty, we've proven that the current path leads nowhere—without exploring any deeper.

The Core Idea:

When we assign a value to variable X, constraints involving X immediately restrict what neighboring variables can be. Forward checking processes these restrictions:

For each constraint involving X and an unassigned variable Y
Remove from Y's domain any values incompatible with X's new value
If Y's domain becomes empty, backtrack immediately

This simple enhancement detects many failures one level earlier than basic backtracking, often pruning vast portions of the search tree.

What You Will Learn

By the end of this page, you'll deeply understand forward checking: how it works, why it's effective, its formal properties, implementation strategies, and when to prefer it over lighter or heavier propagation approaches. You'll see how it naturally combines with variable ordering heuristics for powerful synergy.

From Backtrack Checking to Forward Checking

To appreciate forward checking, let's first understand what it improves upon. Standard backtracking with constraint checking works as follows:

Backtrack Checking (BT):

Select an unassigned variable X
Try a value v from X's domain
Check all constraints involving X and other assigned variables
If no constraint is violated, recurse to the next variable
If a constraint is violated, try another value for X
If all values fail, backtrack to the previous variable

The Problem:

Backtrack checking only detects violations between assigned variables. It cannot detect that a current assignment has made a future variable impossible to satisfy. We continue exploring until we reach that future variable and discover its domain is effectively empty.

Example: 4-Queens

Suppose we place Queen 1 in column 1, Queen 2 in column 3. With basic backtracking:

We don't realize that Queen 3 now cannot be placed in rows covering columns 1, 2, 3, or 4's diagonals
If Queen 3's remaining options are all eliminated by Q1 and Q2's constraints, we won't know until we try Q3
We might explore many values for Q3 (and Q4!) before discovering the inevitable failure

Forward checking would detect Queen 3's empty domain immediately after placing Q2—saving all that exploration.

Backtrack Checking (BT)

•Checks: current variable vs. past variables
•Detection: Finds violation when constraint fully assigned
•Wasted work: May explore many levels before failure
•Domain: Uses original domains throughout
•Failure discovery: Delayed until reaching failed variable

Forward Checking (FC)

•Checks: current variable vs. future variables
•Detection: Finds impossibility one step ahead
•Efficiency: Prunes infeasible values immediately
•Domain: Reduces domains dynamically during search
•Failure discovery: Immediate via empty domain

The Forward Checking Enhancement:

Forward checking extends backtrack checking with one key addition: after assigning X = v, for every unassigned variable Y that shares a constraint with X, remove from Y's domain all values inconsistent with X = v.

This transforms constraint checking from reactive ("did we violate?") to proactive ("what's now impossible?"). The benefits compound: reduced domains lead to fewer branches, which lead to faster search completion.

The Forward Checking Algorithm

Let's formalize forward checking with a precise algorithm. The key data structure is a set of current domains—one for each variable—that shrink as we progress through the search.

Forward Checking Algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
interface ForwardCheckingState<T> {
  assignment: Map<string, T>;       // Current variable assignments
  domains: Map<string, Set<T>>;     // Current (reduced) domains per variable
}
 
function forwardCheckingSearch<T>(csp: CSP<T>): Map<string, T> | null {
  // Initialize with full domains
  const initialDomains = new Map<string, Set<T>>();
  for (const v of csp.variables) {
    initialDomains.set(v, new Set(csp.domains.get(v) || []));
  }
  
  const state: ForwardCheckingState<T> = {
    assignment: new Map(),
    domains: initialDomains
  };
  
  return forwardCheck(state, csp);
}
 
function forwardCheck<T>(
  state: ForwardCheckingState<T>,
  csp: CSP<T>
): Map<string, T> | null {
  const { assignment, domains } = state;
  
  // BASE CASE: All variables assigned = solution found
  if (assignment.size === csp.variables.length) {
    return new Map(assignment);
  }
  
  // SELECT: Choose unassigned variable (MRV heuristic ideal here)
  const variable = selectMRV(assignment, domains, csp);
  
  // Get current domain values for this variable
  const currentDomain = domains.get(variable)!;
  
  for (const value of currentDomain) {
    // CHOOSE: Make the assignment
    assignment.set(variable, value);
    
    // FORWARD CHECK: Prune domains of future variables
    const removals = propagateForward(variable, value, assignment, domains, csp);
    
    // Check if any domain became empty
    const domainWipedOut = checkDomainWipeout(assignment, domains, csp);
    
    if (!domainWipedOut) {
      // EXPLORE: Recurse with reduced domains
      const result = forwardCheck(state, csp);
      if (result !== null) {
        return result;  // Solution found!
      }
    }
    
    // RESTORE: Undo domain reductions (for next value attempt)
    restoreDomains(domains, removals);
    
    // UNCHOOSE: Remove assignment
    assignment.delete(variable);
  }
  
  // All values failed
  return null;
}
 
// The core forward checking operation: reduce neighbor domains
function propagateForward<T>(
  variable: string,
  value: T,
  assignment: Map<string, T>,
  domains: Map<string, Set<T>>,
  csp: CSP<T>
): Array<{ variable: string; value: T }> {  // Returns removed values for restoration
  
  const removals: Array<{ variable: string; value: T }> = [];
  
  // For each constraint involving the just-assigned variable
  for (const constraint of csp.constraints) {
    if (!constraint.variables.includes(variable)) continue;
    
    // For each OTHER unassigned variable in this constraint
    for (const neighbor of constraint.variables) {
      if (neighbor === variable) continue;
      if (assignment.has(neighbor)) continue;  // Already assigned
      
      const neighborDomain = domains.get(neighbor)!;
      const toRemove: T[] = [];
      
      // Check each value in neighbor's domain
      for (const neighborValue of neighborDomain) {
        // Would this assignment be consistent with current assignment?
        const testAssignment = new Map(assignment);
        testAssignment.set(neighbor, neighborValue);
        
        if (!constraint.isSatisfied(testAssignment)) {
          // This value is now IMPOSSIBLE - mark for removal
          toRemove.push(neighborValue);
        }
      }
      
      // Remove impossible values
      for (const v of toRemove) {
        neighborDomain.delete(v);
        removals.push({ variable: neighbor, value: v });
      }
    }
  }
  
  return removals;
}
 
// Check if any unassigned variable has an empty domain
function checkDomainWipeout<T>(
  assignment: Map<string, T>,
  domains: Map<string, Set<T>>,
  csp: CSP<T>
): boolean {
  for (const v of csp.variables) {
    if (assignment.has(v)) continue;
    if (domains.get(v)!.size === 0) {
      return true;  // Domain wipeout detected!
    }
  }
  return false;
}
 
// Restore removed values when backtracking
function restoreDomains<T>(
  domains: Map<string, Set<T>>,
  removals: Array<{ variable: string; value: T }>
): void {
  for (const { variable, value } of removals) {
    domains.get(variable)!.add(value);
  }
}

Algorithm Complexity:

Space: O(nd) for storing current domains, where n = variables, d = max domain size
Time per node: O(c × d) for propagation, where c = constraints involving assigned variable
Total time: Varies wildly based on problem; typically much less than BT despite higher per-node cost

The key insight is that the extra work per node (propagation) pays for itself many times over through avoided nodes (pruned branches).

Visualizing Forward Checking: A Worked Example

Let's trace forward checking on the 4-Queens problem to see how domain reduction works in practice.

Problem Setup:

Variables: Q1, Q2, Q3, Q4 (column position of queen in each row)
Domains: Initially {1, 2, 3, 4} for each
Constraints: No two queens can attack each other

4-Queens Forward Checking Trace

Text

INITIAL STATE:
Q1: {1, 2, 3, 4}
Q2: {1, 2, 3, 4}
Q3: {1, 2, 3, 4}
Q4: {1, 2, 3, 4}
 
═══════════════════════════════════════════════════════════
STEP 1: Assign Q1 = 1 (try first column)
═══════════════════════════════════════════════════════════
 
  1   2   3   4
┌───┬───┬───┬───┐
│ Q │   │   │   │  Row 1: Q1 = 1
├───┼───┼───┼───┤
│   │   │   │   │  Row 2
├───┼───┼───┼───┤
│   │   │   │   │  Row 3
├───┼───┼───┼───┤
│   │   │   │   │  Row 4
└───┴───┴───┴───┘
 
FORWARD CHECK: Propagate Q1=1 to future variables
 
Q2: Remove 1 (same column), Remove 2 (diagonal)
    {1, 2, 3, 4} → {3, 4}
 
Q3: Remove 1 (same column), Remove 3 (diagonal)
    {1, 2, 3, 4} → {2, 4}
 
Q4: Remove 1 (same column), Remove 4 (diagonal)
    {1, 2, 3, 4} → {2, 3}
 
After Q1=1:
Q1: [assigned = 1]
Q2: {3, 4}        ← reduced from 4 to 2 values!
Q3: {2, 4}        ← reduced from 4 to 2 values!
Q4: {2, 3}        ← reduced from 4 to 2 values!
 
No empty domains → continue
 
═══════════════════════════════════════════════════════════
STEP 2: Assign Q2 = 3 (first available value)
═══════════════════════════════════════════════════════════
 
  1   2   3   4
┌───┬───┬───┬───┐
│ Q │   │   │   │  Q1 = 1
├───┼───┼───┼───┤
│   │   │ Q │   │  Q2 = 3
├───┼───┼───┼───┤
│   │   │   │   │
├───┼───┼───┼───┤
│   │   │   │   │
└───┴───┴───┴───┘
 
FORWARD CHECK: Propagate Q2=3 to future variables
 
Q3: Remove 3 (same column), Remove 4 (diagonal from Q2), 
    But 3 already removed by Q1!
    {2, 4} → {2}  (4 removed)
 
Q4: Remove 3 (same column)
    {2, 3} → {2}
 
After Q2=3:
Q1: [assigned = 1]
Q2: [assigned = 3]
Q3: {2}          ← only ONE option left!
Q4: {2}          ← only ONE option left!
 
No empty domains → continue
 
═══════════════════════════════════════════════════════════
STEP 3: Assign Q3 = 2 (only available value)
═══════════════════════════════════════════════════════════
 
  1   2   3   4
┌───┬───┬───┬───┐
│ Q │   │   │   │  Q1 = 1
├───┼───┼───┼───┤
│   │   │ Q │   │  Q2 = 3
├───┼───┼───┼───┤
│   │ Q │   │   │  Q3 = 2
├───┼───┼───┼───┤
│   │   │   │   │
└───┴───┴───┴───┘
 
FORWARD CHECK: Propagate Q3=2 to future variables
 
Q4: Remove 2 (same column)
    {2} → {}      ← EMPTY DOMAIN!
 
DOMAIN WIPEOUT DETECTED!
╔═══════════════════════════════════════════════════════╗
║  Q4 has no valid placement → BACKTRACK IMMEDIATELY    ║
║  We did NOT need to actually try Q4                   ║
╚═══════════════════════════════════════════════════════╝
 
═══════════════════════════════════════════════════════════
BACKTRACK to Q2, try next value Q2 = 4
═══════════════════════════════════════════════════════════
 
(Continue search with Q2 = 4...)

The Power of Early Detection

Notice that forward checking detected failure BEFORE assigning Q4. With basic backtracking, we would have tried to assign Q4, discovered no values work, then backtracked. That's 4 constraint checks saved. In larger problems with larger domains, these savings multiply enormously.

Forward Checking and MRV: A Powerful Synergy

Forward checking and the Minimum Remaining Values (MRV) heuristic form a natural partnership. MRV selects the variable with the smallest current domain. Forward checking maintains current domains by removing impossible values. Together, they create a feedback loop that focuses search on the most constrained parts of the problem.

Why They Work Together:

FC reduces domains → MRV has better information about which variables are most constrained
MRV picks most constrained variable → More likely to fail quickly if path is doomed
Early failure detection → Fewer wasted branches explored
Domain reduction propagates → Each assignment potentially reduces many domains

Without FC, MRV uses static initial domains and can't adapt to the current partial assignment. Without MRV, FC reduces domains but doesn't strategically exploit this information for variable selection.

MRV with Forward Checking
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// MRV heuristic using CURRENT (reduced) domains
function selectMRV<T>(
  assignment: Map<string, T>,
  domains: Map<string, Set<T>>,
  csp: CSP<T>
): string {
  let bestVariable: string | null = null;
  let minDomainSize = Infinity;
  
  for (const variable of csp.variables) {
    // Skip already-assigned variables
    if (assignment.has(variable)) continue;
    
    // Get CURRENT domain size (after forward checking reductions)
    const currentDomainSize = domains.get(variable)!.size;
    
    // Special case: if domain is empty, this path is doomed
    // Still select it so we detect failure immediately
    if (currentDomainSize === 0) {
      return variable;
    }
    
    if (currentDomainSize < minDomainSize) {
      minDomainSize = currentDomainSize;
      bestVariable = variable;
    }
  }
  
  if (bestVariable === null) {
    throw new Error("No unassigned variable found");
  }
  
  return bestVariable;
}
 
// Enhanced MRV with degree tie-breaking
function selectMRVWithDegree<T>(
  assignment: Map<string, T>,
  domains: Map<string, Set<T>>,
  csp: CSP<T>
): string {
  let bestVariable: string | null = null;
  let minDomainSize = Infinity;
  let maxDegree = -1;
  
  for (const variable of csp.variables) {
    if (assignment.has(variable)) continue;
    
    const domainSize = domains.get(variable)!.size;
    
    // Empty domain - select immediately
    if (domainSize === 0) return variable;
    
    // Count unassigned neighbors (degree)
    const degree = countUnassignedNeighbors(variable, assignment, csp);
    
    // MRV primary, degree as tie-breaker
    if (domainSize < minDomainSize ||
        (domainSize === minDomainSize && degree > maxDegree)) {
      minDomainSize = domainSize;
      maxDegree = degree;
      bestVariable = variable;
    }
  }
  
  return bestVariable!;
}
 
function countUnassignedNeighbors<T>(
  variable: string,
  assignment: Map<string, T>,
  csp: CSP<T>
): number {
  const neighbors = new Set<string>();
  
  for (const constraint of csp.constraints) {
    if (!constraint.variables.includes(variable)) continue;
    for (const other of constraint.variables) {
      if (other !== variable && !assignment.has(other)) {
        neighbors.add(other);
      }
    }
  }
  
  return neighbors.size;
}

The Fail-First Principle:

MRV + FC embodies the "fail-first" principle: if part of the search tree is doomed, we want to discover that as quickly as possible. Variables with small domains are most likely to have no valid assignment—selecting them first means we either succeed quickly (few options) or fail quickly (doomed path detected).

Empirical Impact:

Studies consistently show that FC + MRV together outperform either technique alone by large margins. On many benchmark problems:

Basic backtracking: millions of nodes
FC alone: tens of thousands of nodes
MRV alone: hundreds of thousands of nodes
FC + MRV: hundreds to thousands of nodes

The combination can be 1000x faster than basic backtracking.

Dynamic vs Static MRV

Static MRV (without FC) uses initial domain sizes. Dynamic MRV (with FC) uses current reduced domains. Dynamic MRV is strictly more informed and makes better choices. This is why FC enables MRV to reach its full potential.

Limitations of Forward Checking

Forward checking is powerful but not all-powerful. Understanding its limitations helps you know when to apply stronger techniques.

What FC Misses:

Forward checking only examines constraints between the just-assigned variable and unassigned variables. It doesn't consider constraints among unassigned variables. This means it can miss failures that would be detected by looking at the relationship between two future variables.

Example: A Hidden Conflict

Forward Checking Limitation Example

Text

PROBLEM: 3 variables X, Y, Z, all with domain {1, 2}
CONSTRAINTS: 
  - X ≠ Y
  - Y ≠ Z  
  - X ≠ Z
 
STEP 1: Assign X = 1
 
Forward checking reduces:
  Y: {1,2} → {2}    (X=1 rules out Y=1)
  Z: {1,2} → {2}    (X=1 rules out Z=1)
 
No empty domains → FC says "continue!"
 
STEP 2: Assign Y = 2 (only option)
 
Forward checking reduces:
  Z: {2} → {}       (Y=2 rules out Z=2)
 
DOMAIN WIPEOUT! Now we detect failure.
 
BUT... Could we have detected this earlier?
═══════════════════════════════════════════════════════════
After X=1:
  Y = {2}
  Z = {2}
  
Constraint Y ≠ Z means Y and Z can't both be 2!
But FC only checked X against Y and Z, not Y against Z.
 
ARC CONSISTENCY would have detected this:
  Looking at Y-Z constraint with reduced domains:
  Y = {2}, Z = {2}
  For Y=2, is there ANY value in Z that works? 
  Z=2 fails (Y≠Z violated). 
  No remaining Z values work with Y's domain!
  → Failure detected IMMEDIATELY after X=1!
═══════════════════════════════════════════════════════════

The Gap in FC's Vision:

Forward checking is "local" to the current assignment. It propagates one hop—from the assigned variable to its unassigned neighbors. It doesn't propagate transitively: the constraint between Y and Z isn't re-examined when X's assignment reduces their domains.

When This Matters:

Dense constraint graphs: Many variables interconnected means more hidden conflicts between future variables
Tight constraints: Heavily restricted domains make conflicts between future variables more likely
Long constraint chains: A affects B affects C affects D... FC only sees one link at a time

The Solution: Arc Consistency

Arc consistency (covered next page) examines ALL pairs of constrained variables, propagating domain reductions transitively until no more reductions are possible. This catches the Y-Z conflict immediately but at higher computational cost.

The Trade-off

FC is O(cd) per assignment. Arc consistency is O(cd²) or O(cd³) per assignment. FC misses some failures that AC catches. The question is: does the extra pruning from AC save enough search to justify its higher per-node cost? For many practical problems, the answer is yes—but not always.

Forward Checking Variants and Extensions

Several variants of forward checking offer different trade-offs between propagation strength and computational cost.

Partial Look Ahead (PLA):

After forward checking, additionally check if any pair of future variables has become inconsistent (one can't be satisfied given the other's reduced domain). Stronger than FC, weaker than full arc consistency.

Full Look Ahead (FLA):

Maintain arc consistency among all future variables after each assignment. This is essentially "Maintaining Arc Consistency" (MAC) and typically outperforms FC on hard problems.

Real Full Look Ahead (RFLA):

Includes look-ahead from assigned variables to future variables as well as among future variables. The strongest (and most expensive) look-ahead approach.

Forward Checking Variants Comparison
Variant	Scope of Checking	Cost per Node	Pruning Power
FC	Assigned → Unassigned (direct neighbors)	O(c × d)	Medium
PLA	FC + pairs of future variables	O(c × d + n² × d)	Medium-High
FLA/MAC	Full arc consistency among future variables	O(c × d²)	High
RFLA	Full arc consistency including past	O(c × d²) + overhead	Highest

Conflict-Directed Backjumping (CBJ) with FC:

Another enhancement is combining FC with intelligent backtracking. Standard backtracking always returns to the immediately previous variable. CBJ identifies which earlier assignment actually caused the failure and jumps back to that variable directly, skipping irrelevant intermediate choices.

Domain/Value-Driven FC:

Instead of checking all neighbor domains after each assignment, only check neighbors whose domains might actually be affected by the specific value chosen. This optimizes for sparse constraints where many neighbors are unaffected by many values.

Optimized Forward Checking
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// Optimized FC: Only check affected constraints
interface ConstraintSupport<T> {
  constraint: Constraint<T>;
  supports: Map<string, Map<T, Set<T>>>;  // For each var-value, which neighbor values support it
}
 
// Precompute supports for efficient propagation
function precomputeSupports<T>(
  constraint: Constraint<T>,
  domains: Map<string, Set<T>>
): ConstraintSupport<T> {
  const supports = new Map<string, Map<T, Set<T>>>();
  const [var1, var2] = constraint.variables;  // Assuming binary constraint
  
  // For each value in var1, find supporting values in var2
  const var1Supports = new Map<T, Set<T>>();
  for (const val1 of domains.get(var1)!) {
    const supporting = new Set<T>();
    for (const val2 of domains.get(var2)!) {
      const testAssignment = new Map([[var1, val1], [var2, val2]]);
      if (constraint.isSatisfied(testAssignment)) {
        supporting.add(val2);
      }
    }
    var1Supports.set(val1, supporting);
  }
  supports.set(var1, var1Supports);
  
  // Similarly for var2 → var1
  // (omitted for brevity)
  
  return { constraint, supports };
}
 
// When value is removed from var's domain, check if any neighbor value
// has lost all its supports
function propagateWithSupports<T>(
  variable: string,
  removedValue: T,
  support: ConstraintSupport<T>,
  domains: Map<string, Set<T>>,
  removals: Array<{ variable: string; value: T }>
): boolean {  // returns false if domain wipeout
  
  // Find the other variable in this constraint
  const neighbor = support.constraint.variables.find(v => v !== variable)!;
  const neighborDomain = domains.get(neighbor)!;
  
  // For each value in neighbor's domain, check if it was supported by removedValue
  for (const neighborValue of [...neighborDomain]) {
    const oldSupports = support.supports.get(neighbor)?.get(neighborValue);
    if (oldSupports?.has(removedValue)) {
      // This neighbor value may have lost its last support
      // Check if any other value in variable's domain still supports it
      let hasSupport = false;
      for (const varValue of domains.get(variable)!) {
        if (support.supports.get(variable)?.get(varValue)?.has(neighborValue)) {
          hasSupport = true;
          break;
        }
      }
      if (!hasSupport) {
        // No more support! Remove this neighbor value
        neighborDomain.delete(neighborValue);
        removals.push({ variable: neighbor, value: neighborValue });
        
        if (neighborDomain.size === 0) {
          return false;  // Domain wipeout
        }
      }
    }
  }
  
  return true;
}

Implementation Considerations for Efficient FC

Implementing forward checking efficiently requires attention to data structures and algorithmic details. Small implementation choices can result in order-of-magnitude performance differences.

Domain Representation:

Set per variable: Simple, O(1) removal and restoration
Bitset per variable: Cache-efficient for small integer domains, fast copy/restore
Linked list: Supports O(1) removal with trailing for restoration

Trailing for Backtracking:

Rather than copying domains at each branch point (O(nd) memory per node), record only the changes made. On backtrack, undo changes in reverse order. This is called trailing.

Trailing Implementation
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Trailing: Record changes for efficient backtracking
interface Trail<T> {
  operations: Array<{ 
    type: 'remove' | 'assign';
    variable: string;
    value?: T;
    previousDomain?: Set<T>;
  }>;
  mark(): number;          // Returns current position
  restore(mark: number): void;  // Undo all operations since mark
}
 
class TrailedDomains<T> {
  private domains: Map<string, Set<T>>;
  private trail: Array<{ variable: string; value: T }> = [];
  
  constructor(initialDomains: Map<string, Set<T>>) {
    // Deep copy initial domains
    this.domains = new Map();
    for (const [v, d] of initialDomains) {
      this.domains.set(v, new Set(d));
    }
  }
  
  getDomain(variable: string): Set<T> {
    return this.domains.get(variable)!;
  }
  
  removeValue(variable: string, value: T): boolean {
    const domain = this.domains.get(variable)!;
    if (domain.has(value)) {
      domain.delete(value);
      this.trail.push({ variable, value });  // Record for undo
      return domain.size === 0;  // Return true if domain empty
    }
    return false;
  }
  
  getMark(): number {
    return this.trail.length;
  }
  
  restoreToMark(mark: number): void {
    // Undo all removals since the mark
    while (this.trail.length > mark) {
      const { variable, value } = this.trail.pop()!;
      this.domains.get(variable)!.add(value);
    }
  }
}
 
// Usage in FC
function forwardCheckWithTrailing<T>(
  assignment: Map<string, T>,
  domains: TrailedDomains<T>,
  csp: CSP<T>
): Map<string, T> | null {
  if (assignment.size === csp.variables.length) {
    return new Map(assignment);
  }
  
  const variable = selectMRV(assignment, domains, csp);
  const currentDomain = [...domains.getDomain(variable)];
  
  for (const value of currentDomain) {
    const mark = domains.getMark();  // Save trail position
    
    assignment.set(variable, value);
    
    const success = propagateFC(variable, value, assignment, domains, csp);
    
    if (success) {
      const result = forwardCheckWithTrailing(assignment, domains, csp);
      if (result !== null) return result;
    }
    
    // Restore domains to before propagation
    domains.restoreToMark(mark);
    assignment.delete(variable);
  }
  
  return null;
}

Performance Optimization Tips

•Cache constraint lookups: Build a map from variables to their constraints for O(1) access instead of scanning all constraints
•Use incremental checking: Track which domains changed and only re-check affected constraints
•Lazy propagation: Don't propagate to variables that won't be selected soon (less relevant with MRV)
•Specialized constraints: Implement efficient propagators for common constraints (AllDiff, Sum, etc.)
•Avoid allocation: Reuse constraint-checking temporary data structures
•Profile first: Micro-optimizations matter only if propagation is the bottleneck

Summary: Forward Checking in Practice

Forward checking represents a fundamental improvement over basic backtracking by looking one step ahead. Let's consolidate the key insights:

Key Takeaways

•FC propagates consequences of each assignment to unassigned neighbors, removing values that are now impossible. Empty domains trigger immediate backtracking.
•Domain reduction eliminates branches before they're explored. This compounds through the search tree for exponential savings.
•FC + MRV synergize beautifully: FC provides dynamic domain sizes, MRV exploits this for smarter variable selection. Together they embody 'fail-first'.
•FC is local — it only propagates one hop from the assigned variable. It misses conflicts between pairs of future variables.
•Efficient implementation matters: trailing for backtracking, constraint indexing for lookup, and careful data structure choices minimize overhead.
•FC is often the sweet spot for moderate-difficulty problems, balancing propagation power against computational overhead.

What's Next:

The next page explores arc consistency—a stronger form of constraint propagation that addresses FC's limitation of missing inter-future-variable conflicts. Arc consistency propagates transitively until a fixed point is reached, catching failures that FC would miss. We'll see algorithms like AC-3 and understand when the extra propagation cost is justified.

Page Complete

You now deeply understand forward checking: its algorithm, visualization, synergy with MRV, limitations, variants, and implementation considerations. This technique forms the foundation of practical CSP solving and prepares you for the more powerful arc consistency methods explored next.

Forward Checking (Conceptual)

Looking One Step Ahead

The Core Idea:

When we assign a value to variable X, constraints involving X immediately restrict what neighboring variables can be. Forward checking processes these restrictions:

For each constraint involving X and an unassigned variable Y
Remove from Y's domain any values incompatible with X's new value
If Y's domain becomes empty, backtrack immediately

This simple enhancement detects many failures one level earlier than basic backtracking, often pruning vast portions of the search tree.

What You Will Learn

From Backtrack Checking to Forward Checking

To appreciate forward checking, let's first understand what it improves upon. Standard backtracking with constraint checking works as follows:

Backtrack Checking (BT):

Select an unassigned variable X
Try a value v from X's domain
Check all constraints involving X and other assigned variables
If no constraint is violated, recurse to the next variable
If a constraint is violated, try another value for X
If all values fail, backtrack to the previous variable

The Problem:

Example: 4-Queens

Suppose we place Queen 1 in column 1, Queen 2 in column 3. With basic backtracking:

We don't realize that Queen 3 now cannot be placed in rows covering columns 1, 2, 3, or 4's diagonals
If Queen 3's remaining options are all eliminated by Q1 and Q2's constraints, we won't know until we try Q3
We might explore many values for Q3 (and Q4!) before discovering the inevitable failure

Forward checking would detect Queen 3's empty domain immediately after placing Q2—saving all that exploration.

Backtrack Checking (BT)

•Checks: current variable vs. past variables
•Detection: Finds violation when constraint fully assigned
•Wasted work: May explore many levels before failure
•Domain: Uses original domains throughout
•Failure discovery: Delayed until reaching failed variable

Forward Checking (FC)

•Checks: current variable vs. future variables
•Detection: Finds impossibility one step ahead
•Efficiency: Prunes infeasible values immediately
•Domain: Reduces domains dynamically during search
•Failure discovery: Immediate via empty domain

The Forward Checking Enhancement:

The Forward Checking Algorithm

Let's formalize forward checking with a precise algorithm. The key data structure is a set of current domains—one for each variable—that shrink as we progress through the search.

Forward Checking Algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
interface ForwardCheckingState<T> {
  assignment: Map<string, T>;       // Current variable assignments
  domains: Map<string, Set<T>>;     // Current (reduced) domains per variable
}
 
function forwardCheckingSearch<T>(csp: CSP<T>): Map<string, T> | null {
  // Initialize with full domains
  const initialDomains = new Map<string, Set<T>>();
  for (const v of csp.variables) {
    initialDomains.set(v, new Set(csp.domains.get(v) || []));
  }
  
  const state: ForwardCheckingState<T> = {
    assignment: new Map(),
    domains: initialDomains
  };
  
  return forwardCheck(state, csp);
}
 
function forwardCheck<T>(
  state: ForwardCheckingState<T>,
  csp: CSP<T>
): Map<string, T> | null {
  const { assignment, domains } = state;
  
  // BASE CASE: All variables assigned = solution found
  if (assignment.size === csp.variables.length) {
    return new Map(assignment);
  }
  
  // SELECT: Choose unassigned variable (MRV heuristic ideal here)
  const variable = selectMRV(assignment, domains, csp);
  
  // Get current domain values for this variable
  const currentDomain = domains.get(variable)!;
  
  for (const value of currentDomain) {
    // CHOOSE: Make the assignment
    assignment.set(variable, value);
    
    // FORWARD CHECK: Prune domains of future variables
    const removals = propagateForward(variable, value, assignment, domains, csp);
    
    // Check if any domain became empty
    const domainWipedOut = checkDomainWipeout(assignment, domains, csp);
    
    if (!domainWipedOut) {
      // EXPLORE: Recurse with reduced domains
      const result = forwardCheck(state, csp);
      if (result !== null) {
        return result;  // Solution found!
      }
    }
    
    // RESTORE: Undo domain reductions (for next value attempt)
    restoreDomains(domains, removals);
    
    // UNCHOOSE: Remove assignment
    assignment.delete(variable);
  }
  
  // All values failed
  return null;
}
 
// The core forward checking operation: reduce neighbor domains
function propagateForward<T>(
  variable: string,
  value: T,
  assignment: Map<string, T>,
  domains: Map<string, Set<T>>,
  csp: CSP<T>
): Array<{ variable: string; value: T }> {  // Returns removed values for restoration
  
  const removals: Array<{ variable: string; value: T }> = [];
  
  // For each constraint involving the just-assigned variable
  for (const constraint of csp.constraints) {
    if (!constraint.variables.includes(variable)) continue;
    
    // For each OTHER unassigned variable in this constraint
    for (const neighbor of constraint.variables) {
      if (neighbor === variable) continue;
      if (assignment.has(neighbor)) continue;  // Already assigned
      
      const neighborDomain = domains.get(neighbor)!;
      const toRemove: T[] = [];
      
      // Check each value in neighbor's domain
      for (const neighborValue of neighborDomain) {
        // Would this assignment be consistent with current assignment?
        const testAssignment = new Map(assignment);
        testAssignment.set(neighbor, neighborValue);
        
        if (!constraint.isSatisfied(testAssignment)) {
          // This value is now IMPOSSIBLE - mark for removal
          toRemove.push(neighborValue);
        }
      }
      
      // Remove impossible values
      for (const v of toRemove) {
        neighborDomain.delete(v);
        removals.push({ variable: neighbor, value: v });
      }
    }
  }
  
  return removals;
}
 
// Check if any unassigned variable has an empty domain
function checkDomainWipeout<T>(
  assignment: Map<string, T>,
  domains: Map<string, Set<T>>,
  csp: CSP<T>
): boolean {
  for (const v of csp.variables) {
    if (assignment.has(v)) continue;
    if (domains.get(v)!.size === 0) {
      return true;  // Domain wipeout detected!
    }
  }
  return false;
}
 
// Restore removed values when backtracking
function restoreDomains<T>(
  domains: Map<string, Set<T>>,
  removals: Array<{ variable: string; value: T }>
): void {
  for (const { variable, value } of removals) {
    domains.get(variable)!.add(value);
  }
}

Algorithm Complexity:

Space: O(nd) for storing current domains, where n = variables, d = max domain size
Time per node: O(c × d) for propagation, where c = constraints involving assigned variable
Total time: Varies wildly based on problem; typically much less than BT despite higher per-node cost

The key insight is that the extra work per node (propagation) pays for itself many times over through avoided nodes (pruned branches).

Visualizing Forward Checking: A Worked Example

Let's trace forward checking on the 4-Queens problem to see how domain reduction works in practice.

Problem Setup:

Variables: Q1, Q2, Q3, Q4 (column position of queen in each row)
Domains: Initially {1, 2, 3, 4} for each
Constraints: No two queens can attack each other

4-Queens Forward Checking Trace

Text

INITIAL STATE:
Q1: {1, 2, 3, 4}
Q2: {1, 2, 3, 4}
Q3: {1, 2, 3, 4}
Q4: {1, 2, 3, 4}
 
═══════════════════════════════════════════════════════════
STEP 1: Assign Q1 = 1 (try first column)
═══════════════════════════════════════════════════════════
 
  1   2   3   4
┌───┬───┬───┬───┐
│ Q │   │   │   │  Row 1: Q1 = 1
├───┼───┼───┼───┤
│   │   │   │   │  Row 2
├───┼───┼───┼───┤
│   │   │   │   │  Row 3
├───┼───┼───┼───┤
│   │   │   │   │  Row 4
└───┴───┴───┴───┘
 
FORWARD CHECK: Propagate Q1=1 to future variables
 
Q2: Remove 1 (same column), Remove 2 (diagonal)
    {1, 2, 3, 4} → {3, 4}
 
Q3: Remove 1 (same column), Remove 3 (diagonal)
    {1, 2, 3, 4} → {2, 4}
 
Q4: Remove 1 (same column), Remove 4 (diagonal)
    {1, 2, 3, 4} → {2, 3}
 
After Q1=1:
Q1: [assigned = 1]
Q2: {3, 4}        ← reduced from 4 to 2 values!
Q3: {2, 4}        ← reduced from 4 to 2 values!
Q4: {2, 3}        ← reduced from 4 to 2 values!
 
No empty domains → continue
 
═══════════════════════════════════════════════════════════
STEP 2: Assign Q2 = 3 (first available value)
═══════════════════════════════════════════════════════════
 
  1   2   3   4
┌───┬───┬───┬───┐
│ Q │   │   │   │  Q1 = 1
├───┼───┼───┼───┤
│   │   │ Q │   │  Q2 = 3
├───┼───┼───┼───┤
│   │   │   │   │
├───┼───┼───┼───┤
│   │   │   │   │
└───┴───┴───┴───┘
 
FORWARD CHECK: Propagate Q2=3 to future variables
 
Q3: Remove 3 (same column), Remove 4 (diagonal from Q2), 
    But 3 already removed by Q1!
    {2, 4} → {2}  (4 removed)
 
Q4: Remove 3 (same column)
    {2, 3} → {2}
 
After Q2=3:
Q1: [assigned = 1]
Q2: [assigned = 3]
Q3: {2}          ← only ONE option left!
Q4: {2}          ← only ONE option left!
 
No empty domains → continue
 
═══════════════════════════════════════════════════════════
STEP 3: Assign Q3 = 2 (only available value)
═══════════════════════════════════════════════════════════
 
  1   2   3   4
┌───┬───┬───┬───┐
│ Q │   │   │   │  Q1 = 1
├───┼───┼───┼───┤
│   │   │ Q │   │  Q2 = 3
├───┼───┼───┼───┤
│   │ Q │   │   │  Q3 = 2
├───┼───┼───┼───┤
│   │   │   │   │
└───┴───┴───┴───┘
 
FORWARD CHECK: Propagate Q3=2 to future variables
 
Q4: Remove 2 (same column)
    {2} → {}      ← EMPTY DOMAIN!
 
DOMAIN WIPEOUT DETECTED!
╔═══════════════════════════════════════════════════════╗
║  Q4 has no valid placement → BACKTRACK IMMEDIATELY    ║
║  We did NOT need to actually try Q4                   ║
╚═══════════════════════════════════════════════════════╝
 
═══════════════════════════════════════════════════════════
BACKTRACK to Q2, try next value Q2 = 4
═══════════════════════════════════════════════════════════
 
(Continue search with Q2 = 4...)

The Power of Early Detection

Forward Checking and MRV: A Powerful Synergy

Why They Work Together:

FC reduces domains → MRV has better information about which variables are most constrained
MRV picks most constrained variable → More likely to fail quickly if path is doomed
Early failure detection → Fewer wasted branches explored
Domain reduction propagates → Each assignment potentially reduces many domains

MRV with Forward Checking
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// MRV heuristic using CURRENT (reduced) domains
function selectMRV<T>(
  assignment: Map<string, T>,
  domains: Map<string, Set<T>>,
  csp: CSP<T>
): string {
  let bestVariable: string | null = null;
  let minDomainSize = Infinity;
  
  for (const variable of csp.variables) {
    // Skip already-assigned variables
    if (assignment.has(variable)) continue;
    
    // Get CURRENT domain size (after forward checking reductions)
    const currentDomainSize = domains.get(variable)!.size;
    
    // Special case: if domain is empty, this path is doomed
    // Still select it so we detect failure immediately
    if (currentDomainSize === 0) {
      return variable;
    }
    
    if (currentDomainSize < minDomainSize) {
      minDomainSize = currentDomainSize;
      bestVariable = variable;
    }
  }
  
  if (bestVariable === null) {
    throw new Error("No unassigned variable found");
  }
  
  return bestVariable;
}
 
// Enhanced MRV with degree tie-breaking
function selectMRVWithDegree<T>(
  assignment: Map<string, T>,
  domains: Map<string, Set<T>>,
  csp: CSP<T>
): string {
  let bestVariable: string | null = null;
  let minDomainSize = Infinity;
  let maxDegree = -1;
  
  for (const variable of csp.variables) {
    if (assignment.has(variable)) continue;
    
    const domainSize = domains.get(variable)!.size;
    
    // Empty domain - select immediately
    if (domainSize === 0) return variable;
    
    // Count unassigned neighbors (degree)
    const degree = countUnassignedNeighbors(variable, assignment, csp);
    
    // MRV primary, degree as tie-breaker
    if (domainSize < minDomainSize ||
        (domainSize === minDomainSize && degree > maxDegree)) {
      minDomainSize = domainSize;
      maxDegree = degree;
      bestVariable = variable;
    }
  }
  
  return bestVariable!;
}
 
function countUnassignedNeighbors<T>(
  variable: string,
  assignment: Map<string, T>,
  csp: CSP<T>
): number {
  const neighbors = new Set<string>();
  
  for (const constraint of csp.constraints) {
    if (!constraint.variables.includes(variable)) continue;
    for (const other of constraint.variables) {
      if (other !== variable && !assignment.has(other)) {
        neighbors.add(other);
      }
    }
  }
  
  return neighbors.size;
}

The Fail-First Principle:

Empirical Impact:

Studies consistently show that FC + MRV together outperform either technique alone by large margins. On many benchmark problems:

Basic backtracking: millions of nodes
FC alone: tens of thousands of nodes
MRV alone: hundreds of thousands of nodes
FC + MRV: hundreds to thousands of nodes

The combination can be 1000x faster than basic backtracking.

Dynamic vs Static MRV

Limitations of Forward Checking

Forward checking is powerful but not all-powerful. Understanding its limitations helps you know when to apply stronger techniques.

What FC Misses:

Example: A Hidden Conflict

Forward Checking Limitation Example

Text

PROBLEM: 3 variables X, Y, Z, all with domain {1, 2}
CONSTRAINTS: 
  - X ≠ Y
  - Y ≠ Z  
  - X ≠ Z
 
STEP 1: Assign X = 1
 
Forward checking reduces:
  Y: {1,2} → {2}    (X=1 rules out Y=1)
  Z: {1,2} → {2}    (X=1 rules out Z=1)
 
No empty domains → FC says "continue!"
 
STEP 2: Assign Y = 2 (only option)
 
Forward checking reduces:
  Z: {2} → {}       (Y=2 rules out Z=2)
 
DOMAIN WIPEOUT! Now we detect failure.
 
BUT... Could we have detected this earlier?
═══════════════════════════════════════════════════════════
After X=1:
  Y = {2}
  Z = {2}
  
Constraint Y ≠ Z means Y and Z can't both be 2!
But FC only checked X against Y and Z, not Y against Z.
 
ARC CONSISTENCY would have detected this:
  Looking at Y-Z constraint with reduced domains:
  Y = {2}, Z = {2}
  For Y=2, is there ANY value in Z that works? 
  Z=2 fails (Y≠Z violated). 
  No remaining Z values work with Y's domain!
  → Failure detected IMMEDIATELY after X=1!
═══════════════════════════════════════════════════════════

The Gap in FC's Vision:

When This Matters:

Dense constraint graphs: Many variables interconnected means more hidden conflicts between future variables
Tight constraints: Heavily restricted domains make conflicts between future variables more likely
Long constraint chains: A affects B affects C affects D... FC only sees one link at a time

The Solution: Arc Consistency

The Trade-off

Forward Checking Variants and Extensions

Several variants of forward checking offer different trade-offs between propagation strength and computational cost.

Partial Look Ahead (PLA):

Full Look Ahead (FLA):

Maintain arc consistency among all future variables after each assignment. This is essentially "Maintaining Arc Consistency" (MAC) and typically outperforms FC on hard problems.

Real Full Look Ahead (RFLA):

Includes look-ahead from assigned variables to future variables as well as among future variables. The strongest (and most expensive) look-ahead approach.

Forward Checking Variants Comparison
Variant	Scope of Checking	Cost per Node	Pruning Power
FC	Assigned → Unassigned (direct neighbors)	O(c × d)	Medium
PLA	FC + pairs of future variables	O(c × d + n² × d)	Medium-High
FLA/MAC	Full arc consistency among future variables	O(c × d²)	High
RFLA	Full arc consistency including past	O(c × d²) + overhead	Highest

Conflict-Directed Backjumping (CBJ) with FC:

Domain/Value-Driven FC:

Optimized Forward Checking
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// Optimized FC: Only check affected constraints
interface ConstraintSupport<T> {
  constraint: Constraint<T>;
  supports: Map<string, Map<T, Set<T>>>;  // For each var-value, which neighbor values support it
}
 
// Precompute supports for efficient propagation
function precomputeSupports<T>(
  constraint: Constraint<T>,
  domains: Map<string, Set<T>>
): ConstraintSupport<T> {
  const supports = new Map<string, Map<T, Set<T>>>();
  const [var1, var2] = constraint.variables;  // Assuming binary constraint
  
  // For each value in var1, find supporting values in var2
  const var1Supports = new Map<T, Set<T>>();
  for (const val1 of domains.get(var1)!) {
    const supporting = new Set<T>();
    for (const val2 of domains.get(var2)!) {
      const testAssignment = new Map([[var1, val1], [var2, val2]]);
      if (constraint.isSatisfied(testAssignment)) {
        supporting.add(val2);
      }
    }
    var1Supports.set(val1, supporting);
  }
  supports.set(var1, var1Supports);
  
  // Similarly for var2 → var1
  // (omitted for brevity)
  
  return { constraint, supports };
}
 
// When value is removed from var's domain, check if any neighbor value
// has lost all its supports
function propagateWithSupports<T>(
  variable: string,
  removedValue: T,
  support: ConstraintSupport<T>,
  domains: Map<string, Set<T>>,
  removals: Array<{ variable: string; value: T }>
): boolean {  // returns false if domain wipeout
  
  // Find the other variable in this constraint
  const neighbor = support.constraint.variables.find(v => v !== variable)!;
  const neighborDomain = domains.get(neighbor)!;
  
  // For each value in neighbor's domain, check if it was supported by removedValue
  for (const neighborValue of [...neighborDomain]) {
    const oldSupports = support.supports.get(neighbor)?.get(neighborValue);
    if (oldSupports?.has(removedValue)) {
      // This neighbor value may have lost its last support
      // Check if any other value in variable's domain still supports it
      let hasSupport = false;
      for (const varValue of domains.get(variable)!) {
        if (support.supports.get(variable)?.get(varValue)?.has(neighborValue)) {
          hasSupport = true;
          break;
        }
      }
      if (!hasSupport) {
        // No more support! Remove this neighbor value
        neighborDomain.delete(neighborValue);
        removals.push({ variable: neighbor, value: neighborValue });
        
        if (neighborDomain.size === 0) {
          return false;  // Domain wipeout
        }
      }
    }
  }
  
  return true;
}

Implementation Considerations for Efficient FC

Implementing forward checking efficiently requires attention to data structures and algorithmic details. Small implementation choices can result in order-of-magnitude performance differences.

Domain Representation:

Set per variable: Simple, O(1) removal and restoration
Bitset per variable: Cache-efficient for small integer domains, fast copy/restore
Linked list: Supports O(1) removal with trailing for restoration

Trailing for Backtracking:

Rather than copying domains at each branch point (O(nd) memory per node), record only the changes made. On backtrack, undo changes in reverse order. This is called trailing.

Trailing Implementation
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// Trailing: Record changes for efficient backtracking
interface Trail<T> {
  operations: Array<{ 
    type: 'remove' | 'assign';
    variable: string;
    value?: T;
    previousDomain?: Set<T>;
  }>;
  mark(): number;          // Returns current position
  restore(mark: number): void;  // Undo all operations since mark
}
 
class TrailedDomains<T> {
  private domains: Map<string, Set<T>>;
  private trail: Array<{ variable: string; value: T }> = [];
  
  constructor(initialDomains: Map<string, Set<T>>) {
    // Deep copy initial domains
    this.domains = new Map();
    for (const [v, d] of initialDomains) {
      this.domains.set(v, new Set(d));
    }
  }
  
  getDomain(variable: string): Set<T> {
    return this.domains.get(variable)!;
  }
  
  removeValue(variable: string, value: T): boolean {
    const domain = this.domains.get(variable)!;
    if (domain.has(value)) {
      domain.delete(value);
      this.trail.push({ variable, value });  // Record for undo
      return domain.size === 0;  // Return true if domain empty
    }
    return false;
  }
  
  getMark(): number {
    return this.trail.length;
  }
  
  restoreToMark(mark: number): void {
    // Undo all removals since the mark
    while (this.trail.length > mark) {
      const { variable, value } = this.trail.pop()!;
      this.domains.get(variable)!.add(value);
    }
  }
}
 
// Usage in FC
function forwardCheckWithTrailing<T>(
  assignment: Map<string, T>,
  domains: TrailedDomains<T>,
  csp: CSP<T>
): Map<string, T> | null {
  if (assignment.size === csp.variables.length) {
    return new Map(assignment);
  }
  
  const variable = selectMRV(assignment, domains, csp);
  const currentDomain = [...domains.getDomain(variable)];
  
  for (const value of currentDomain) {
    const mark = domains.getMark();  // Save trail position
    
    assignment.set(variable, value);
    
    const success = propagateFC(variable, value, assignment, domains, csp);
    
    if (success) {
      const result = forwardCheckWithTrailing(assignment, domains, csp);
      if (result !== null) return result;
    }
    
    // Restore domains to before propagation
    domains.restoreToMark(mark);
    assignment.delete(variable);
  }
  
  return null;
}

Performance Optimization Tips

•Cache constraint lookups: Build a map from variables to their constraints for O(1) access instead of scanning all constraints
•Use incremental checking: Track which domains changed and only re-check affected constraints
•Lazy propagation: Don't propagate to variables that won't be selected soon (less relevant with MRV)
•Specialized constraints: Implement efficient propagators for common constraints (AllDiff, Sum, etc.)
•Avoid allocation: Reuse constraint-checking temporary data structures
•Profile first: Micro-optimizations matter only if propagation is the bottleneck

Summary: Forward Checking in Practice

Forward checking represents a fundamental improvement over basic backtracking by looking one step ahead. Let's consolidate the key insights:

Key Takeaways

•FC propagates consequences of each assignment to unassigned neighbors, removing values that are now impossible. Empty domains trigger immediate backtracking.
•Domain reduction eliminates branches before they're explored. This compounds through the search tree for exponential savings.
•FC + MRV synergize beautifully: FC provides dynamic domain sizes, MRV exploits this for smarter variable selection. Together they embody 'fail-first'.
•FC is local — it only propagates one hop from the assigned variable. It misses conflicts between pairs of future variables.
•Efficient implementation matters: trailing for backtracking, constraint indexing for lookup, and careful data structure choices minimize overhead.
•FC is often the sweet spot for moderate-difficulty problems, balancing propagation power against computational overhead.

What's Next:

Page Complete