General Constraint Satisfaction Framework - Constraint Satisfaction & Pruning | OneNoughtOne

0/361

Data Structures & AlgorithmsConstraint Satisfaction & Pruning

Constraint Satisfaction & Pruning

LevelAdvanced

Duration90 mins

TopicConstraint Satisfaction & Pruning

1 / 4

General Constraint Satisfaction Framework

When Problems Become Puzzles

Imagine you're scheduling a conference with hundreds of talks, dozens of rooms, and thousands of constraints: speaker availability, room capacity, equipment requirements, attendee conflicts, and sponsor preferences. Each decision affects others in complex ways. A naive approach would generate all possible schedules and filter valid ones—but with 200 talks and 20 rooms, you'd face 20²⁰⁰ possibilities, more than atoms in the observable universe.

This is not an abstract academic exercise. It's exactly the kind of problem that software engineers face daily: task scheduling, resource allocation, configuration management, game AI, and countless optimization challenges. What these problems share is a rich structure of constraints—rules that valid solutions must satisfy.

Constraint Satisfaction Problems (CSPs) provide a powerful framework for modeling these challenges. More than just a theoretical construct, CSPs give us a language to describe combinatorial problems precisely, and a toolkit of algorithms that exploit problem structure to find solutions efficiently. The connection to backtracking is deep: CSPs formalize what backtracking does intuitively, and open the door to systematic optimizations that transform intractable problems into solvable ones.

What You Will Learn

By the end of this page, you will understand the formal structure of constraint satisfaction problems, how to model real-world challenges as CSPs, the deep relationship between CSPs and backtracking, and why this framework enables powerful optimization techniques that we'll explore in subsequent pages.

What Is a Constraint Satisfaction Problem?

A Constraint Satisfaction Problem (CSP) is a mathematical framework for describing problems where we must assign values to variables under certain restrictions. Formally, a CSP consists of three components:

1. Variables (X): A finite set of variables X = {X₁, X₂, ..., Xₙ}, each representing a decision to be made.

2. Domains (D): For each variable Xᵢ, a domain Dᵢ specifies the possible values that variable can take. The domain can be finite (like {1, 2, 3, 4}) or, in more advanced settings, infinite or continuous.

3. Constraints (C): A set of constraints, where each constraint specifies which combinations of values for a subset of variables are allowed. Constraints encode the "rules" of the problem.

A solution to a CSP is an assignment of values to all variables such that every constraint is satisfied. Many problems ask for:

Any solution (satisfiability)
All solutions (enumeration)
An optimal solution (when combined with an objective function, becoming a Constraint Optimization Problem)

The Power of Declarative Modeling

CSPs separate the what from the how. You declare your variables, domains, and constraints—describing what makes a solution valid—and let algorithms figure out how to find solutions. This declarative approach is far more powerful than writing imperative search code, because the same CSP algorithms work across vastly different problem domains.

Constraint Types:

Constraints come in many forms, each with different properties that affect solving strategies:

Unary Constraints: Restrict a single variable's values. Example: "Variable X₁ cannot be 5" reduces X₁'s domain.

Binary Constraints: Restrict pairs of variables. Example: "X₁ ≠ X₂" (different values) or "X₁ < X₂" (ordering). Binary constraints are the most common and well-studied.

Higher-Order Constraints (n-ary): Restrict three or more variables simultaneously. Example: "All of X₁, X₂, X₃ must be different" (an all-different constraint).

Global Constraints: Capture complex patterns involving many variables. Examples include AllDifferent (all variables take distinct values), Sum (variables sum to a target), and Cardinality (counting occurrences). Global constraints are crucial for practical CSP solving because they enable specialized propagation algorithms.

Common Constraint Types in CSP Modeling
Constraint Type	Variables Involved	Example	Typical Usage
Unary	1	X₁ ≠ 3	Domain restrictions, initial filtering
Binary (Equality)	2	X₁ = X₂	Variable linking, symmetry
Binary (Inequality)	2	X₁ ≠ X₂	Graph coloring, scheduling conflicts
Binary (Ordering)	2	X₁ < X₂	Precedence, sequencing
AllDifferent	n	All variables distinct	Sudoku, Latin squares, assignment
Sum/Linear	n	X₁ + X₂ + X₃ = 10	Resource allocation, knapsack
Element	3+	Y = Array[X]	Array indexing, lookups
Table/Extensional	any	Allowed tuples listed	Arbitrary relations

The Constraint Graph: Visualizing Problem Structure

Every CSP has an underlying structure that can be visualized as a constraint graph (for binary constraints) or a constraint hypergraph (for higher-order constraints). Understanding this structure is essential for choosing effective solving strategies.

For binary CSPs:

Each variable becomes a node
Each binary constraint becomes an edge connecting the constrained variables
The graph structure reveals dependencies and potential solution strategies

Example: Map Coloring

Consider coloring a map of Australia with three colors (Red, Green, Blue) such that no adjacent regions share a color:

Variables: WA (Western Australia), NT (Northern Territory), SA (South Australia), Q (Queensland), NSW (New South Wales), V (Victoria), T (Tasmania)
Domains: {R, G, B} for each variable
Constraints: WA ≠ NT, WA ≠ SA, NT ≠ SA, NT ≠ Q, SA ≠ Q, SA ≠ NSW, SA ≠ V, Q ≠ NSW, NSW ≠ V

The constraint graph mirrors the geographical adjacency graph—each edge represents a shared border.

Map Coloring CSP Structure
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
// CSP Representation for Map Coloring
interface CSP<T> {
  variables: string[];
  domains: Map<string, T[]>;
  constraints: Constraint<T>[];
}
 
interface Constraint<T> {
  variables: string[];  // Variables involved in this constraint
  isSatisfied: (assignment: Map<string, T>) => boolean;
}
 
// Create the Australia map coloring CSP
function createAustraliaCSP(): CSP<string> {
  const variables = ['WA', 'NT', 'SA', 'Q', 'NSW', 'V', 'T'];
  const colors = ['R', 'G', 'B'];
  
  // All regions can be any color initially
  const domains = new Map<string, string[]>();
  for (const v of variables) {
    domains.set(v, [...colors]);
  }
  
  // Adjacent regions must have different colors
  const adjacencies: [string, string][] = [
    ['WA', 'NT'], ['WA', 'SA'],
    ['NT', 'SA'], ['NT', 'Q'],
    ['SA', 'Q'], ['SA', 'NSW'], ['SA', 'V'],
    ['Q', 'NSW'],
    ['NSW', 'V']
  ];
  
  const constraints: Constraint<string>[] = adjacencies.map(([v1, v2]) => ({
    variables: [v1, v2],
    isSatisfied: (assignment: Map<string, string>) => {
      const val1 = assignment.get(v1);
      const val2 = assignment.get(v2);
      // Constraint is satisfied if either is unassigned, or they differ
      if (val1 === undefined || val2 === undefined) return true;
      return val1 !== val2;
    }
  }));
  
  return { variables, domains, constraints };
}

Why Graph Structure Matters:

The constraint graph reveals crucial information about problem difficulty and solution strategies:

Connectivity: Disconnected components can be solved independently and solutions combined.

Density: Sparse graphs (few constraints) have more solutions; dense graphs are more constrained and often harder.

Tree-width: If the constraint graph is a tree (acyclic), the CSP can be solved in polynomial time! Graph-based algorithms exploit low tree-width for efficiency.

Cliques: Highly connected subgraphs indicate tightly coupled variables that must be carefully coordinated.

Understanding your problem's constraint structure is the first step to choosing effective algorithms. A problem that looks intractable might have exploitable structure that makes it easy.

CSP as a Universal Problem Language

One of the remarkable properties of the CSP framework is its universality. An enormous variety of problems can be naturally expressed as CSPs, from puzzles to scheduling to configuration. This means algorithms developed for CSPs apply broadly—a single solver can tackle thousands of different problem types.

Let's see how classic problems map to the CSP framework:

Classic Problems as CSPs

•N-Queens: Variables X₁...Xₙ represent column positions for queens in each row. Domains {1...n}. Constraints: no two queens on same column (Xᵢ ≠ Xⱼ), no two on same diagonal (|Xᵢ - Xⱼ| ≠ |i - j|).
•Sudoku: 81 variables (one per cell), domains {1...9} initially (reduced for given values), constraints for rows, columns, and 3×3 boxes enforcing all-different.
•Graph Coloring: Variables for vertices, domains for colors, inequality constraints for adjacent vertices.
•Job Shop Scheduling: Variables for task start times, domains for time slots, constraints for precedence, machine capacity, and deadlines.
•Boolean Satisfiability (SAT): Variables for Boolean propositions, domains {True, False}, constraints for clauses in CNF form. SAT is a special case of CSP with binary domains.
•Cryptarithmetic Puzzles: SEND + MORE = MONEY: Variables for digits, all-different constraint, arithmetic constraints.

N-Queens as CSP
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
// N-Queens as a CSP
function createNQueensCSP(n: number): CSP<number> {
  // Variables: Q1, Q2, ..., Qn (column position for queen in each row)
  const variables = Array.from({ length: n }, (_, i) => `Q${i + 1}`);
  
  // Domains: each queen can be in any column 1 to n
  const domains = new Map<string, number[]>();
  for (const v of variables) {
    domains.set(v, Array.from({ length: n }, (_, i) => i + 1));
  }
  
  const constraints: Constraint<number>[] = [];
  
  // For each pair of queens
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const v1 = variables[i];
      const v2 = variables[j];
      const rowDiff = j - i;  // Distance in rows
      
      constraints.push({
        variables: [v1, v2],
        isSatisfied: (assignment: Map<string, number>) => {
          const col1 = assignment.get(v1);
          const col2 = assignment.get(v2);
          if (col1 === undefined || col2 === undefined) return true;
          
          // Same column check
          if (col1 === col2) return false;
          
          // Diagonal check: |col difference| must not equal row difference
          if (Math.abs(col1 - col2) === rowDiff) return false;
          
          return true;
        }
      });
    }
  }
  
  return { variables, domains, constraints };
}
 
// For 8-Queens:
// - 8 variables (one per row)
// - Each domain has 8 values (columns 1-8)
// - 28 pairwise constraints (8 choose 2 = 28)

Modeling is Key

The same problem can often be modeled as a CSP in multiple ways. Better models lead to faster solutions. In N-Queens, using one variable per row (with column as value) is superior to using one variable per cell (with {queen/empty} values) because it implicitly enforces the one-queen-per-row constraint and has a much smaller search space.

The Deep Connection to Backtracking

Backtracking algorithms and CSPs are two sides of the same coin. Every backtracking algorithm can be viewed as a CSP solver, and every CSP naturally leads to a backtracking solution strategy. Understanding this connection clarifies both concepts and reveals optimization opportunities.

Standard Backtracking as CSP Solving:

The backtracking template we've studied—choose, explore, unchoose—maps directly to CSP operations:

Choose: Select an unassigned variable and assign it a value from its domain
Check: Verify all constraints involving the newly assigned variable
Explore: Recursively solve the remaining, smaller CSP
Unchoose: If exploration fails, remove the assignment and try another value
Backtrack: If no values work, return failure and let the caller try different earlier choices

This is exactly what backtracking does, just expressed in CSP vocabulary.

Generic CSP Backtracking Solver
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
// Generic backtracking solver for any CSP
function backtrackingSearch<T>(csp: CSP<T>): Map<string, T> | null {
  return backtrack(new Map(), csp);
}
 
function backtrack<T>(
  assignment: Map<string, T>,
  csp: CSP<T>
): Map<string, T> | null {
  // Base case: all variables assigned = solution found
  if (assignment.size === csp.variables.length) {
    return new Map(assignment);  // Return copy of solution
  }
  
  // SELECT: Choose an unassigned variable
  const variable = selectUnassignedVariable(assignment, csp);
  
  // ORDER: Get domain values (possibly ordered by heuristics)
  const values = orderDomainValues(variable, assignment, csp);
  
  for (const value of values) {
    // CHOOSE: Assign value to variable
    assignment.set(variable, value);
    
    // CHECK: Verify constraints
    if (isConsistent(assignment, csp)) {
      // EXPLORE: Recurse on remaining problem
      const result = backtrack(assignment, csp);
      if (result !== null) {
        return result;  // Solution found!
      }
    }
    
    // UNCHOOSE: Remove assignment for next attempt
    assignment.delete(variable);
  }
  
  // BACKTRACK: No value worked, return failure
  return null;
}
 
function selectUnassignedVariable<T>(
  assignment: Map<string, T>,
  csp: CSP<T>
): string {
  // Simple: return first unassigned variable
  // Better: use MRV (minimum remaining values) heuristic
  for (const v of csp.variables) {
    if (!assignment.has(v)) return v;
  }
  throw new Error("No unassigned variable");
}
 
function orderDomainValues<T>(
  variable: string,
  assignment: Map<string, T>,
  csp: CSP<T>
): T[] {
  // Simple: return domain in order
  // Better: use LCV (least constraining value) heuristic
  return csp.domains.get(variable) || [];
}
 
function isConsistent<T>(
  assignment: Map<string, T>,
  csp: CSP<T>
): boolean {
  // Check all constraints involving assigned variables
  for (const constraint of csp.constraints) {
    // Only check constraints where all variables are assigned
    const allAssigned = constraint.variables.every(v => assignment.has(v));
    if (allAssigned && !constraint.isSatisfied(assignment)) {
      return false;
    }
  }
  return true;
}

The Search Tree Perspective:

Every CSP defines a search tree that backtracking explores:

Root: Empty assignment (no variables assigned)
Nodes: Partial assignments (some variables assigned)
Edges: Extending an assignment with one more variable-value pair
Leaves: Complete assignments (all variables assigned) or failures (constraint violated)
Solutions: Complete assignments where all constraints are satisfied

The depth of this tree equals the number of variables. The branching factor at each level equals the domain size of the chosen variable. The total search space without pruning is:

$$\text{Search space} = \prod_{i=1}^{n} |D_i|$$

For n variables each with domain size d, this gives d^n nodes—exponential in the number of variables. The goal of all CSP optimization techniques is to prune this tree, avoiding exploration of branches that cannot contain solutions.

The Exponential Challenge

CSPs are generally NP-complete (reducible from SAT). There's no polynomial-time algorithm that solves all CSPs. But intelligent pruning, constraint propagation, and heuristics can make many practical problems tractable. The difference between naive backtracking and optimized CSP solving can be the difference between years of computation and milliseconds.

Variable and Value Ordering Heuristics

While constraints define what is valid, ordering heuristics determine how we explore the search space. The order in which we assign variables and try values dramatically affects performance—often by orders of magnitude. Good heuristics make smart choices that either find solutions quickly or reveal failures early.

Variable Ordering: Which Variable to Assign Next?

Variable Ordering Heuristics

•Minimum Remaining Values (MRV): Choose the variable with the fewest legal values remaining in its domain. Intuition: This variable is most constrained and most likely to cause failure—detect failures early. Also called 'fail-first' heuristic. This is the most important ordering heuristic.
•Degree Heuristic: Choose the variable involved in the most constraints with unassigned variables. Intuition: This variable affects the most remaining decisions—constrain them early. Useful as a tie-breaker for MRV.
•Most Constrained Variable: Similar to degree, but considers constraint tightness, not just count. Variables with more restrictive constraints are chosen first.

Value Ordering: Which Value to Try First?

Value Ordering Heuristics

•Least Constraining Value (LCV): For the chosen variable, try values that rule out the fewest choices for neighboring variables. Intuition: Maximize flexibility for future assignments—increase the chance that remaining variables can be assigned.
•Geelen's Promise: Choose values that create the most solutions in the remaining subproblem. More sophisticated but harder to compute.
•Domain-Specific Ordering: In some problems, domain knowledge suggests good orderings. For example, in scheduling, earlier time slots might be preferred.

MRV and LCV Heuristics
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
// Minimum Remaining Values (MRV) Variable Ordering
function selectByMRV<T>(
  assignment: Map<string, T>,
  csp: CSP<T>,
  domains: Map<string, T[]>  // Current reduced domains
): string {
  let bestVariable: string | null = null;
  let minRemainingValues = Infinity;
  
  for (const variable of csp.variables) {
    if (assignment.has(variable)) continue;
    
    const remaining = domains.get(variable)?.length ?? 0;
    
    // Choose variable with fewest remaining values
    if (remaining < minRemainingValues) {
      minRemainingValues = remaining;
      bestVariable = variable;
    }
  }
  
  if (bestVariable === null) {
    throw new Error("No unassigned variable");
  }
  
  return bestVariable;
}
 
// Least Constraining Value (LCV) Value Ordering
function orderByLCV<T>(
  variable: string,
  assignment: Map<string, T>,
  csp: CSP<T>,
  domains: Map<string, T[]>
): T[] {
  const values = domains.get(variable) || [];
  
  // Count how many values each choice rules out for neighbors
  const valueScores: Array<{ value: T; ruledOut: number }> = [];
  
  for (const value of values) {
    let ruledOut = 0;
    
    // Find neighbors (variables sharing a constraint with this one)
    for (const constraint of csp.constraints) {
      if (!constraint.variables.includes(variable)) continue;
      
      for (const neighbor of constraint.variables) {
        if (neighbor === variable || assignment.has(neighbor)) continue;
        
        // Count how many of neighbor's values would be ruled out
        const neighborDomain = domains.get(neighbor) || [];
        for (const nv of neighborDomain) {
          const testAssignment = new Map(assignment);
          testAssignment.set(variable, value);
          testAssignment.set(neighbor, nv);
          if (!constraint.isSatisfied(testAssignment)) {
            ruledOut++;
          }
        }
      }
    }
    
    valueScores.push({ value, ruledOut });
  }
  
  // Sort by least constraining (fewest ruled out) first
  valueScores.sort((a, b) => a.ruledOut - b.ruledOut);
  
  return valueScores.map(vs => vs.value);
}

Why Opposite Strategies?

Notice that variable and value ordering use opposite philosophies. For variables, we're pessimistic: choose the most constrained variable to fail early if the path is doomed. For values, we're optimistic: choose the least constraining value to maximize our chances of success. This combination—fail-fast variable selection with keep-options-open value selection—is remarkably effective across diverse problems.

Consistency and Propagation: A Preview

The most powerful optimization techniques for CSPs go beyond just ordering—they actively reduce domains based on constraint analysis. This is called constraint propagation or consistency enforcement.

The Key Insight:

When we make an assignment X₁ = v, other constraints become more restrictive. Values in other variables' domains that are now impossible can be removed before we try them. If a domain becomes empty, we know immediately that this path leads nowhere—no need to continue exploring.

Types of Consistency:

Node Consistency: Every value in a variable's domain satisfies all unary constraints on that variable. This is easy to enforce upfront by filtering domains.

Arc Consistency: For every pair of constrained variables (X, Y), every value in X's domain has at least one compatible value in Y's domain. If value x ∈ Dₓ has no compatible value in Dᵧ, we can remove x from Dₓ.

Path Consistency, k-Consistency, and beyond: Higher levels of consistency involve more variables simultaneously, offering more pruning but at higher computational cost.

Without Propagation

•Assign variable, check constraints
•Discover failures only when all involved variables are assigned
•Many wasted explorations of doomed paths
•Exponential search even for easy problems
•Constraint violations detected late

With Propagation

•Assign variable, propagate implications
•Immediately reduce other domains
•Empty domain = early failure detection
•Vast pruning of search space
•Constraint violations detected early

Example: Sudoku with Arc Consistency

Consider a Sudoku where a cell has candidates {1, 2, 5}. If through propagation we discover:

The 1 in this cell's row is forced elsewhere
The 5 in this cell's column is forced elsewhere

We can immediately reduce this cell's domain to {2}. This single value then propagates to all cells in its row, column, and box—potentially solving large portions of the puzzle without any backtracking.

Propagation transforms Sudoku from a problem requiring extensive search into one often solvable by propagation alone. Most newspaper Sudokus are designed to be solvable with arc consistency and naked/hidden singles—no actual backtracking needed.

In the following pages, we'll explore pruning techniques, forward checking, and arc consistency in depth. These concepts transform CSP solving from exponential enumeration into intelligent constraint-driven search.

Real-World CSP Applications

The CSP framework isn't just academic theory—it powers countless real-world systems. Understanding CSPs opens doors to solving practical problems across industries.

CSP Applications Across Industries
Domain	Problem	Variables	Constraints
Transportation	Vehicle routing	Route segments	Capacity, time windows, driver hours
Manufacturing	Production scheduling	Task start times	Precedence, machine capacity, deadlines
Telecommunications	Frequency allocation	Channel assignments	Interference avoidance, coverage
Education	Exam timetabling	Exam slots	Room capacity, student conflicts, spreads
Software	Configuration management	Component versions	Compatibility, dependencies, features
Sports	Tournament scheduling	Match times/venues	Team availability, TV slots, travel
Retail	Shelf space allocation	Product placements	Visibility, affinity, capacity
Healthcare	Nurse rostering	Shift assignments	Coverage, preferences, regulations

Industry Impact

Companies like Google OR-Tools, IBM CPLEX, and Gurobi provide industrial-strength CSP/constraint programming solvers used by Fortune 500 companies. A single optimization improvement in airline crew scheduling or supply chain logistics can save millions of dollars annually. CSP is not just theory—it's a multi-billion dollar applied field.

Summary: The CSP Framework

We've established the theoretical and practical foundation for understanding constraint satisfaction problems. Let's consolidate the key insights:

Key Takeaways

•CSPs formalize combinatorial problems with three components: variables, domains, and constraints. This declarative approach separates problem specification from solution strategy.
•Constraint graphs reveal structure that algorithms can exploit. Tree-structured CSPs are solvable in polynomial time; dense graphs are harder but may have other exploitable patterns.
•CSPs are universal — countless problems from Sudoku to scheduling map naturally to the framework, enabling reuse of general-purpose algorithms.
•Backtracking is CSP solving — the choose/explore/unchoose pattern directly implements variable assignment search over the CSP's constraint-defined space.
•Ordering heuristics matter enormously — MRV (fail-first variable selection) and LCV (keep-options-open value selection) provide massive speedups over arbitrary ordering.
•Constraint propagation is the key to scalability — actively reducing domains based on constraint implications prunes the search space far beyond what passive checking achieves.

What's Next:

Now that we understand the CSP framework, we're ready to explore the techniques that make CSP solving practical at scale. The next page dives deep into pruning techniques—strategies that eliminate entire branches of the search tree before they're explored, transforming exponential problems into tractable ones.

Page Complete

You now understand the constraint satisfaction framework—variables, domains, constraints, and their connection to backtracking search. This foundation prepares you to master the powerful optimization techniques ahead: pruning, forward checking, and arc consistency. The journey from exponential to practical begins here.