Constraint Satisfaction - Learning Module

Loading content...

0/276

Pruning Techniques to Reduce Search

The Art of Not Looking

Consider searching for a solution in a tree with 10 billion nodes. If you could examine one million nodes per second, you'd need nearly three hours. But what if intelligent analysis could eliminate 99.99% of those nodes before you ever visit them? Suddenly, your search takes mere seconds.

This is the power of pruning—the systematic elimination of search space regions that provably cannot contain solutions. Pruning doesn't find solutions faster by examining nodes faster; it finds solutions faster by not examining most nodes at all.

The Fundamental Insight:

Most nodes in a backtracking search tree lead to dead ends. They represent partial solutions that will eventually violate some constraint. Naive backtracking discovers this only after exploring deep into a doomed branch. Pruning techniques detect doom early—sometimes at the moment a bad decision is made, sometimes before it's even considered.

In this page, we'll explore the spectrum of pruning strategies, from simple constraint checking improvements to sophisticated propagation techniques. Each layer of sophistication trades computation time (for pruning analysis) against exploration time (for search). The art lies in finding the right balance for your problem.

What You Will Learn

By the end of this page, you'll understand the hierarchy of pruning techniques, from feasibility checking through domain reduction to constraint propagation. You'll know when to apply each technique, how to implement them efficiently, and how to reason about their cost-benefit tradeoffs.

The Pruning Principle

Pruning in search algorithms means proving that a subtree cannot contain any solutions and therefore skipping its exploration entirely. The search tree still conceptually contains these nodes, but we never visit them.

Why Pruning Works:

Constraints create dependencies between variables. When we make an assignment X₁ = v, the constraints involving X₁ restrict what values other variables can take. If these restrictions eliminate all possibilities for some future variable, then no matter what choices we make for other variables, we'll eventually fail at that empty-domain variable.

The key insight: we can detect this failure now, rather than after making many more choices.

The Pruning Trade-off:

Pruning is not free. Detecting that a branch is doomed requires computation. The question is whether the computation saved by not exploring the branch exceeds the computation spent detecting its doom.

Light pruning: Quick checks that eliminate obvious failures
Heavy pruning: Expensive analysis that eliminates subtle failures
No pruning: Just explore everything (baseline backtracking)

The optimal strategy depends on your problem's structure. Dense constraints favor heavy pruning (many failures to detect). Sparse constraints may favor lighter approaches.

Pruning Visualization

Text

Search Tree without Pruning:
=====================================
                    Root
                   /    \
                  A      B
                 /|\    /|\
                1 2 3  4 5 6
               ... ... ... ...
               
All branches explored, even doomed ones.
Total nodes visited: Thousands to billions
 
Search Tree WITH Pruning:
=====================================
                    Root
                   /    \
                  A      B (pruned - constraint violation detected)
                 /|\      ╳
                1 2 3
               /  |  \
              ...  ╳  ╳   (pruned - domains would become empty)
              
Only viable branches explored.
Total nodes visited: Often orders of magnitude fewer
 
The power of pruning: Not avoiding slow paths,
but avoiding MOST paths entirely.

Exponential Impact

If pruning eliminates a fraction f of nodes at each level, and the tree has depth d, then the total nodes visited is reduced by factor (1-f)^d. Even modest per-level pruning (say, 50%) compounds to eliminate 99.9% of a 10-level tree. This exponential impact is why pruning transforms intractable problems into solvable ones.

Feasibility Pruning: The First Line of Defense

The simplest form of pruning is feasibility checking—verifying that the current partial assignment doesn't already violate any constraint. This is so fundamental that most backtracking implementations include it implicitly.

Basic Feasibility Check:

After making an assignment Xᵢ = v, check all constraints involving Xᵢ. If any constraint is violated (meaning all its variables are assigned but the constraint predicate fails), immediately backtrack.

The Limitation:

Basic feasibility checking only detects violations when all variables in a constraint are assigned. Binary constraints are detected after two assignments; higher-order constraints even later. We may make many doomed decisions before detecting failure.

Feasibility Pruning Implementation
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
// Basic feasibility pruning: check constraints after assignment
function isFeasible<T>(
  assignment: Map<string, T>,
  csp: CSP<T>,
  justAssigned: string  // The variable we just assigned
): boolean {
  // Check only constraints involving the just-assigned variable
  for (const constraint of csp.constraints) {
    if (!constraint.variables.includes(justAssigned)) continue;
    
    // Check if ALL variables in this constraint are now assigned
    const allAssigned = constraint.variables.every(v => assignment.has(v));
    
    if (allAssigned) {
      // Fully instantiated constraint - must be satisfied
      if (!constraint.isSatisfied(assignment)) {
        return false;  // PRUNE: This path is doomed
      }
    }
    // If not all assigned, constraint can't be checked yet
    // (This is the limitation of basic feasibility checking)
  }
  
  return true;  // No violation detected (yet)
}
 
// Backtracking with feasibility pruning
function backtrackWithFeasibility<T>(
  assignment: Map<string, T>,
  csp: CSP<T>
): Map<string, T> | null {
  if (assignment.size === csp.variables.length) {
    return new Map(assignment);
  }
  
  const variable = selectUnassignedVariable(assignment, csp);
  const domain = csp.domains.get(variable) || [];
  
  for (const value of domain) {
    assignment.set(variable, value);
    
    // PRUNING CHECK: Verify feasibility before recursing
    if (isFeasible(assignment, csp, variable)) {
      const result = backtrackWithFeasibility(assignment, csp);
      if (result !== null) return result;
    }
    // If not feasible, we don't recurse - that's the pruning!
    
    assignment.delete(variable);
  }
  
  return null;
}

Enhanced Feasibility: Partial Constraint Checking

We can be smarter. Many constraints can detect partial violations before all variables are assigned. For example:

X₁ ≠ X₂: If X₁ = 5 and we're about to assign X₂ = 5, we can detect the violation immediately
X₁ < X₂: If X₁ = 10 and X₂'s remaining domain is {1, 2, 3}, we know this path is doomed
Sum(Xᵢ) = 100: If the assigned variables already sum to 110, no further assignments can satisfy the constraint

Partial checking requires constraints to expose more information than just a boolean satisfaction test. Many CSP libraries define constraints with separate methods for:

isSatisfied(assignment) — Complete check when all variables assigned
isPossible(assignment) — Partial check that detects early violations
propagate(assignment) — Domain reduction based on current assignment

The Cost of Checking

Feasibility checking has overhead. If your constraints are expensive to evaluate, checking them frequently can slow things down. For very fast constraints (like integer comparisons), check eagerly. For expensive constraints (like database lookups or complex calculations), check strategically.

Domain Reduction: Shrinking Possibilities

Domain reduction goes beyond checking for violations—it actively removes values from unassigned variables' domains when those values cannot possibly appear in any solution.

The Insight:

When we assign X₁ = v, this assignment creates implications for other variables. Values in their domains that are inconsistent with X₁ = v can be removed. When we later consider those variables, we only try the remaining values—saving all the time we'd spend exploring doomed branches from the removed values.

The Key Question:

For each unassigned variable Xⱼ and each value w in its domain, ask: "Given the current assignment, is there any way for Xⱼ = w to participate in a complete, valid solution?" If the answer is provably no, remove w from Xⱼ's domain.

Domain Reduction Concept
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
// Domain state: tracks current domains during search
interface DomainState<T> {
  domains: Map<string, Set<T>>;  // Current valid values per variable
  
  clone(): DomainState<T>;      // For branching
  removeValue(variable: string, value: T): boolean;  // Returns true if domain became empty
  getDomain(variable: string): Set<T>;
}
 
// Basic domain reduction after an assignment
function reduceDomains<T>(
  assignment: Map<string, T>,
  domainState: DomainState<T>,
  assignedVar: string,
  assignedValue: T,
  csp: CSP<T>
): boolean {  // Returns false if any domain becomes empty (failure detection)
  
  // For each constraint involving the assigned variable
  for (const constraint of csp.constraints) {
    if (!constraint.variables.includes(assignedVar)) continue;
    
    // For each OTHER variable in this constraint
    for (const otherVar of constraint.variables) {
      if (otherVar === assignedVar) continue;
      if (assignment.has(otherVar)) continue;  // Already assigned
      
      // Check each value in the other variable's domain
      const otherDomain = domainState.getDomain(otherVar);
      const toRemove: T[] = [];
      
      for (const otherValue of otherDomain) {
        // Would this value be consistent with the current assignment?
        const testAssignment = new Map(assignment);
        testAssignment.set(otherVar, otherValue);
        
        if (!constraint.isSatisfied(testAssignment)) {
          // This value is INCOMPATIBLE with current assignment
          toRemove.push(otherValue);
        }
      }
      
      // Remove incompatible values
      for (const value of toRemove) {
        if (domainState.removeValue(otherVar, value)) {
          return false;  // Domain became empty! Failure detected early
        }
      }
    }
  }
  
  return true;  // No domain became empty
}

Domain Reduction in Action: N-Queens Example

Consider placing the first queen on an 8×8 board at position (row 1, column 4):

Before placement:

Q₂ (row 2) can be columns {1, 2, 3, 4, 5, 6, 7, 8}
Q₃ (row 3) can be columns {1, 2, 3, 4, 5, 6, 7, 8}
...and so on

After placing Q₁ = 4:

Q₂ excludes: column 4 (same column), columns 3 and 5 (diagonal)
Q₂ domain becomes: {1, 2, 6, 7, 8}
Q₃ excludes: column 4 (same column), columns 2 and 6 (diagonal from Q₁)
Q₃ domain becomes: {1, 3, 5, 7, 8}

We've eliminated 3 values from Q₂'s domain and 3 from Q₃'s. Those 6 branches will never be explored. As we continue, these reductions compound.

Empty Domain = Instant Failure:

If at any point a variable's domain becomes empty, we know immediately that the current path cannot lead to a solution. We backtrack right away, without exploring any deeper.

Domain Management Complexity

Domain reduction requires careful bookkeeping. When we backtrack, we must restore the domains to their previous state. Strategies include: (1) full domain copying before each branch (memory-intensive), (2) recording changes and undoing them on backtrack (trailing), or (3) recomputing domains from scratch after backtrack (recomputation). The choice depends on domain sizes and branching factors.

Bounds Pruning: Leveraging Numeric Constraints

When domains are numeric intervals rather than small discrete sets, explicit enumeration is impractical. Bounds pruning maintains just the minimum and maximum possible values for each variable and propagates these bounds through constraints.

The Technique:

Instead of tracking every possible value, track only:

min[X]: The smallest value X can take
max[X]: The largest value X can take

When a constraint links variables, it creates relationships between their bounds. For example:

For X + Y = 10:

min[X] = 10 - max[Y]
max[X] = 10 - min[Y]

For X ≤ Y:

max[X] ≤ max[Y]
min[Y] ≥ min[X]

Propagating these relationships tightens bounds across the constraint network.

Bounds Propagation
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
interface Bounds {
  min: number;
  max: number;
}
 
interface BoundsState {
  bounds: Map<string, Bounds>;
  
  updateMin(variable: string, newMin: number): boolean;  // Returns true if changed
  updateMax(variable: string, newMax: number): boolean;
  isEmpty(variable: string): boolean;  // min > max means empty
}
 
// Example: Propagate bounds for X + Y = sum constraint
function propagateSumConstraint(
  x: string,
  y: string, 
  sum: number,
  state: BoundsState
): boolean {  // Returns false if any bounds become invalid
  
  let changed = true;
  while (changed) {
    changed = false;
    
    const xBounds = state.bounds.get(x)!;
    const yBounds = state.bounds.get(y)!;
    
    // min[X] >= sum - max[Y]
    const newMinX = sum - yBounds.max;
    if (state.updateMin(x, newMinX)) changed = true;
    
    // max[X] <= sum - min[Y]
    const newMaxX = sum - yBounds.min;
    if (state.updateMax(x, newMaxX)) changed = true;
    
    // Similarly for Y
    const newMinY = sum - xBounds.max;
    if (state.updateMin(y, newMinY)) changed = true;
    
    const newMaxY = sum - xBounds.min;
    if (state.updateMax(y, newMaxY)) changed = true;
    
    // Check for failures
    if (state.isEmpty(x) || state.isEmpty(y)) {
      return false;  // Bounds became invalid - prune!
    }
  }
  
  return true;  // Bounds are consistent
}
 
// Example: Propagate bounds for X < Y constraint  
function propagateLessThanConstraint(
  x: string,
  y: string,
  state: BoundsState
): boolean {
  
  const xBounds = state.bounds.get(x)!;
  const yBounds = state.bounds.get(y)!;
  
  // max[X] must be less than max[Y]
  // Actually: max[X] < max[Y], but for integers: max[X] <= max[Y] - 1
  state.updateMax(x, yBounds.max - 1);
  
  // min[Y] must be greater than min[X]
  // For integers: min[Y] >= min[X] + 1
  state.updateMin(y, xBounds.min + 1);
  
  return !state.isEmpty(x) && !state.isEmpty(y);
}

When Bounds Pruning Shines:

Integer programming problems: Resource allocation, scheduling with time windows
Optimization problems: When combined with branch-and-bound
Continuous domains: Where explicit enumeration is impossible
Linear constraints: Sum, difference, product constraints have clean bound propagation rules

Bounds Consistency:

A CSP is bounds consistent if, for every variable, the minimum and maximum values of its domain can be extended to a complete solution. Bounds consistency is weaker than full arc consistency but much cheaper to maintain for large numeric domains.

Combining with Branch-and-Bound

In optimization problems, bounds pruning combines naturally with branch-and-bound. The best solution found so far provides a bound that prunes branches whose best possible value can't improve on it. This combination is the foundation of modern integer programming solvers.

Symmetry Breaking: Eliminating Equivalent Searches

Many problems have symmetries—transformations that map solutions to other solutions. Without special handling, the search explores all symmetric variants of each partial solution, wasting enormous effort.

Common Symmetries:

Variable Symmetry: If variables are interchangeable, permuting them gives equivalent solutions. Example: In bin packing, bins are indistinguishable—packing items into bins 1,2,3 is the same as packing into 3,1,2.

Value Symmetry: If values are interchangeable, using different values gives equivalent solutions. Example: In graph coloring, {R,G,B} and {G,R,B} color assignments are essentially the same—just relabeled.

Geometric Symmetry: Rotations and reflections map solutions to solutions. Example: In N-Queens, rotating or reflecting the board gives an equivalent solution.

Symmetry Breaking Techniques
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
// Example 1: Variable Symmetry Breaking (Ordering)
// For indistinguishable variables, impose an ordering constraint
 
// In bin packing: Force items to be assigned to lower-numbered bins first
function binPackingSymmetryBreaking(
  items: number[],      // Item sizes
  binCapacity: number,
  numBins: number
): Constraint<number>[] {
  const constraints: Constraint<number>[] = [];
  
  // Each item goes to some bin (1 to numBins)
  // Symmetry breaking: item i can only use bin j if some item < i uses bin j-1
  // Simpler version: first item uses bin 1
  constraints.push({
    variables: ['item_0'],
    isSatisfied: (a) => a.get('item_0') === 1
  });
  
  // Each subsequent item uses a bin ≤ max bin used so far, or max+1
  // This prevents exploring equivalent bin permutations
  
  return constraints;
}
 
// Example 2: Value Symmetry Breaking (First-Use Ordering)
// For graph coloring: assign colors in order of first appearance
function coloringSymmetryBreaking(
  vertices: string[],
  numColors: number
): Constraint<number>[] {
  const constraints: Constraint<number>[] = [];
  
  // First vertex gets color 1
  constraints.push({
    variables: [vertices[0]],
    isSatisfied: (a) => a.get(vertices[0]) === 1
  });
  
  // Each vertex uses a color already used, or the next unused color
  // i.e., vertex i can use color c only if c <= max(colors[0..i-1]) + 1
  for (let i = 1; i < vertices.length; i++) {
    const prevVerts = vertices.slice(0, i);
    constraints.push({
      variables: [...prevVerts, vertices[i]],
      isSatisfied: (a) => {
        const myColor = a.get(vertices[i]);
        if (myColor === undefined) return true;
        
        const prevColors = prevVerts
          .map(v => a.get(v))
          .filter(c => c !== undefined) as number[];
        
        if (prevColors.length === 0) return myColor === 1;
        
        const maxPrev = Math.max(...prevColors);
        return myColor <= maxPrev + 1;
      }
    });
  }
  
  return constraints;
}
 
// Example 3: Geometric Symmetry Breaking (N-Queens)
// Remove rotational/reflectional symmetry by constraining first queen position
function nQueensSymmetryBreaking(n: number): Constraint<number>[] {
  const constraints: Constraint<number>[] = [];
  
  // Force Q1 to be in the left half of the board
  // This eliminates the horizontal reflection symmetry
  constraints.push({
    variables: ['Q1'],
    isSatisfied: (a) => {
      const col = a.get('Q1');
      if (col === undefined) return true;
      return col <= Math.ceil(n / 2);
    }
  });
  
  // Could also add: when Q1 is in middle column, force Q2 to upper half
  // This handles the remaining symmetries
  
  return constraints;
}

Static vs Dynamic Symmetry Breaking:

Static symmetry breaking adds constraints at the start that eliminate symmetric solutions. These are called lex-leader constraints (keeping only the lexicographically smallest representative of each equivalence class).

Dynamic symmetry breaking detects symmetries during search. When we find that value v fails for variable X, and v' is symmetric to v, we can prune v' without trying it. Techniques include:

Symmetry breaking during search (SBDS)
Symmetry breaking via dominance detection (SBDD)
Coset search for permutation groups

Impact:

Symmetry breaking can reduce search by factors equal to the symmetry group size. For a problem with n! variable symmetry (like permutation problems), this can mean n! less search—astronomical savings.

Incomplete Symmetry Breaking

Adding symmetry-breaking constraints can slow down propagation (more constraints to check). Also, complex symmetry groups may require many constraints to fully break. Sometimes it's better to break only the most common symmetries and accept some duplicate exploration.

Nogood Learning: Remembering Failures

When backtracking fails, it often fails for a specific reason—a particular combination of assignments that together violate constraints. A nogood is a partial assignment that cannot be extended to a solution. Nogood learning records these failures to avoid repeating them.

Why This Matters:

Consider a search where we discover that assigning X₁ = 3 and X₅ = 7 together leads to failure (perhaps they force X₁₀ to have an empty domain). Standard backtracking unassigns and tries alternatives. But later in the search, we might reach the same X₁ = 3, X₅ = 7 combination via a different path—and fail again for the same reason.

Nogood learning records {X₁ = 3, X₅ = 7} as a nogood. Any partial assignment containing this combination is immediately prunable.

Nogood Learning
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
87
88
89
type Nogood<T> = Map<string, T>;  // A forbidden partial assignment
 
interface NogoodStore<T> {
  nogoods: Nogood<T>[];
  
  // Add a learned nogood
  addNogood(nogood: Nogood<T>): void;
  
  // Check if current assignment contains any nogood
  containsNogood(assignment: Map<string, T>): boolean;
}
 
function createNogoodStore<T>(): NogoodStore<T> {
  const nogoods: Nogood<T>[] = [];
  
  return {
    nogoods,
    
    addNogood(nogood: Nogood<T>) {
      // Could check for subsumption: don't add if existing nogood is subset
      nogoods.push(nogood);
    },
    
    containsNogood(assignment: Map<string, T>): boolean {
      for (const nogood of nogoods) {
        // Check if all entries in nogood are present in assignment
        let matches = true;
        for (const [variable, value] of nogood) {
          if (assignment.get(variable) !== value) {
            matches = false;
            break;
          }
        }
        if (matches) return true;  // Found a matching nogood!
      }
      return false;
    }
  };
}
 
// Conflict-Directed Backjumping with Nogood Learning
function backtrackWithNogoods<T>(
  assignment: Map<string, T>,
  csp: CSP<T>,
  store: NogoodStore<T>,
  conflictVars: Set<string>[]  // Track which variables caused each constraint failure
): Map<string, T> | null {
  
  if (assignment.size === csp.variables.length) {
    return new Map(assignment);
  }
  
  // Check for known nogood before exploring
  if (store.containsNogood(assignment)) {
    return null;  // We've been here before and it failed
  }
  
  const variable = selectUnassignedVariable(assignment, csp);
  const domain = csp.domains.get(variable) || [];
  
  const localConflicts = new Set<string>();
  
  for (const value of domain) {
    assignment.set(variable, value);
    
    if (isConsistent(assignment, csp)) {
      const result = backtrackWithNogoods(assignment, csp, store, conflictVars);
      if (result !== null) return result;
      
      // Collect conflicts from failed subtree
      // (In full implementation, this comes from analyzing the failure)
    }
    
    assignment.delete(variable);
  }
  
  // All values failed - learn a nogood from the conflicts
  const nogood = new Map<string, T>();
  for (const conflictVar of localConflicts) {
    if (assignment.has(conflictVar)) {
      nogood.set(conflictVar, assignment.get(conflictVar)!);
    }
  }
  if (nogood.size > 0) {
    store.addNogood(nogood);
  }
  
  return null;
}

Clause Learning in SAT:

Nogood learning originated in SAT solving, where it's called conflict-driven clause learning (CDCL). Modern SAT solvers learn thousands to millions of clauses during search. Each learned clause prunes part of the remaining search space.

The key insight in CDCL is conflict analysis—when a failure occurs, analyze why it failed to construct a minimal nogood. This is done by resolution: tracing back through the implication graph to find the root causes of the conflict.

Practical Considerations:

Memory: Storing many nogoods uses memory. Solvers periodically forget less useful nogoods.
Lookup cost: Checking against many nogoods takes time. Efficient data structures (watched literals) minimize this.
Nogood size: Smaller nogoods are more valuable (prune more). Learning algorithms try to find minimal nogoods.
Relevance: Nogoods involving the current decision variables are most useful. Irrelevant ones rarely fire.

The SAT Revolution

Conflict-driven clause learning, combined with restarts and efficient data structures, transformed SAT solving. Problems with millions of variables that seemed hopeless in the 1990s are now routinely solved in seconds. This technology underlies verification tools, planning systems, and many optimization applications.

The Pruning Hierarchy: From Light to Heavy

Different pruning techniques trade effort for effectiveness. Understanding this hierarchy helps you choose the right approach for your problem.

Pruning Techniques Comparison
Technique	Cost per Node	Pruning Power	When to Use
No pruning	O(1)	None	Never (baseline only)
Feasibility check	O(c) where c = constraints	Low	Always as minimum
Forward checking	O(c × d) where d = domain size	Medium	Binary constraints, small domains
Arc consistency (AC-3)	O(c × d²)	High	Dense constraints, needs propagation
Arc consistency (AC-4)	O(c × d²) but better in practice	High	When AC-3 is too slow
Path consistency	O(n³ × d³)	Very high	Rarely - usually overkill
Global constraint propagation	Varies	Highest for applicable constraints	When using global constraints
Nogood learning	Amortized over search	Can be transformative	Long searches, repeated subproblems
Full lookahead	O(c × d^k)	Maximum	Almost never - too expensive

Light Pruning (Fast, Less Powerful)

•Quick feasibility checks
•Forward checking (next page)
•Low overhead per node
•Best for: sparse constraints, simple domains
•May miss many pruning opportunities

Heavy Pruning (Slower, More Powerful)

•Full arc consistency maintenance
•Path consistency or higher
•High overhead per node
•Best for: dense constraints, large domains
•Explores far fewer nodes overall

Choosing the Right Level:

The optimal pruning level depends on:

Constraint density: More constraints → heavier pruning pays off
Domain sizes: Larger domains → more values to prune → heavier pruning helps
Search tree depth: Deeper trees → pruning has more time to compound
Constraint types: Some constraints (like AllDifferent) have specialized propagators that make heavy pruning cheap
Solution density: Few solutions → need to search more → heavier pruning helps

In practice, maintaining arc consistency (MAC) or forward checking with MRV are common defaults that work well across many problems. Tune from there based on profiling.

Summary: The Power of Pruning

We've explored the rich landscape of pruning techniques that transform exponential search into practical computation. Let's consolidate the key insights:

Key Takeaways

•Pruning eliminates search space by detecting doomed branches before exploration, not by searching faster within branches.
•Feasibility checking is the minimum—always verify constraints before recursing. Enhanced checks can detect partial violations early.
•Domain reduction actively shrinks domains, turning value elimination into search elimination. Empty domains signal immediate failure.
•Bounds pruning handles numeric domains efficiently by propagating min/max intervals through constraints.
•Symmetry breaking eliminates redundant search of equivalent solution classes, with savings proportional to symmetry group size.
•Nogood learning remembers why failures occurred, preventing the same mistake via different paths. This is the core of modern SAT solving.
•The pruning hierarchy trades computation for effectiveness—choose based on your problem's constraints, domains, and solution density.

What's Next:

The next page focuses on forward checking—a specific and widely-used pruning technique that strikes an excellent balance between simplicity and effectiveness. Forward checking reduces domains of unassigned variables immediately when assignments are made, detecting failures one step ahead rather than waiting for all constraint variables to be assigned.

Page Complete

You now understand the spectrum of pruning techniques available for CSP solving. From simple feasibility checks to sophisticated nogood learning, these techniques share a common goal: avoid exploring doomed search branches. Next, we'll dive deep into forward checking—your first step toward practical constraint propagation.