45:"/_next/static/chunks/33yus346z0l_n.js" 46:"/_next/static/chunks/2j22cxchii_xx.js" 47:"/_next/static/chunks/0iv56yrji_20j.js" 48:"/_next/static/chunks/32izpn90gvm22.js" 49:"/_next/static/chunks/3j8bi-zu9bqs4.js" 4a:"/_next/static/chunks/1z-pox7hqp2x3.js" 4b:"/_next/static/chunks/20w4eaqlekefm.js" 4c:"/_next/static/chunks/1tn-0fivsxsv1.js" 4d:"/_next/static/chunks/09nq57stwzkgf.js" 4e:"/_next/static/chunks/3m1xjj5kw5fie.js" 4f:"/_next/static/chunks/0gafyzg9j9yqj.js" 50:"/_next/static/chunks/3k2gyg36fnag_.js" 51:"/_next/static/chunks/3bgoyiso1rhn7.js" 52:"/_next/static/chunks/3cstd6xzfli_o.js" 53:"/_next/static/chunks/253gnmj0-cj17.js" 54:"/_next/static/chunks/0hlb44ca7-4a2.js" 55:"/_next/static/chunks/20329i6m_04t6.js" 56:"/_next/static/chunks/40mq7ggq-ozo4.js" 57:"/_next/static/chunks/082jo-0ajazgr.js" 58:"/_next/static/chunks/2ozcrjb_hh74t.js" 59:"/_next/static/chunks/01a-3hvnqu8wl.js" 5a:"/_next/static/chunks/05i8en-x14ibi.js" 5b:"/_next/static/chunks/3m0r7x0jt5wm7.js" 5c:"/_next/static/chunks/2k8pepwc4pxns.js" 5d:"/_next/static/chunks/0wa9m1-tphf9u.js" 5e:"/_next/static/chunks/30jdm3dwz834g.js" 5f:"/_next/static/chunks/0k9bl6dipnsvu.js" 60:"/_next/static/chunks/18ggtgz2yf759.js" 61:"/_next/static/chunks/0i3-eynrkvqi7.js" 62:I[593304,["$2a","$2b","$2c","$2d","$2e","$2f","$45","$46","$47","$48","$49","$4a","$4b","$4c","$4d","$4e","$4f","$50","$51","$52","$53","$54","$55","$56","$57","$58","$59","$5a","$5b","$5c","$5d","$5e","$5f","$60","$61"],"OwnedHydration"] 63:T505,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.64:T41c,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)65:T547,// CSP Representation for Map Coloring interface CSP { variables: string[]; domains: Map; constraints: Constraint[]; } interface Constraint { variables: string[]; // Variables involved in this constraint isSatisfied: (assignment: Map) => boolean; } // Create the Australia map coloring CSP function createAustraliaCSP(): CSP { 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(); 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[] = adjacencies.map(([v1, v2]) => ({ variables: [v1, v2], isSatisfied: (assignment: Map) => { 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 }; }66:T622,from typing import TypeVar, Generic, Dict, List, Callable, Optional from dataclasses import dataclass T = TypeVar('T') @dataclass class Constraint(Generic[T]): """Represents a constraint over one or more variables.""" variables: List[str] is_satisfied: Callable[[Dict[str, T]], bool] @dataclass class CSP(Generic[T]): """Constraint Satisfaction Problem representation.""" variables: List[str] domains: Dict[str, List[T]] constraints: List[Constraint[T]] def create_australia_csp() -> CSP[str]: """Create the Australia map coloring CSP.""" variables = ['WA', 'NT', 'SA', 'Q', 'NSW', 'V', 'T'] colors = ['R', 'G', 'B'] # All regions can be any color initially domains = {v: colors[:] for v in variables} # Adjacent regions must have different colors adjacencies = [ ('WA', 'NT'), ('WA', 'SA'), ('NT', 'SA'), ('NT', 'Q'), ('SA', 'Q'), ('SA', 'NSW'), ('SA', 'V'), ('Q', 'NSW'), ('NSW', 'V') ] def make_not_equal_constraint(v1: str, v2: str) -> Constraint[str]: def is_satisfied(assignment: Dict[str, str]) -> bool: val1 = assignment.get(v1) val2 = assignment.get(v2) # Satisfied if either unassigned or they differ if val1 is None or val2 is None: return True return val1 != val2 return Constraint([v1, v2], is_satisfied) constraints = [make_not_equal_constraint(v1, v2) for v1, v2 in adjacencies] return CSP(variables, domains, constraints)67:T5a7,// N-Queens as a CSP function createNQueensCSP(n: number): CSP { // 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(); for (const v of variables) { domains.set(v, Array.from({ length: n }, (_, i) => i + 1)); } const constraints: Constraint[] = []; // 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) => { 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)68:T88a,// Generic backtracking solver for any CSP function backtrackingSearch(csp: CSP): Map | null { return backtrack(new Map(), csp); } function backtrack( assignment: Map, csp: CSP ): Map | 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( assignment: Map, csp: CSP ): 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( variable: string, assignment: Map, csp: CSP ): T[] { // Simple: return domain in order // Better: use LCV (least constraining value) heuristic return csp.domains.get(variable) || []; } function isConsistent( assignment: Map, csp: CSP ): 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; }69:T913,def backtracking_search(csp: CSP[T]) -> Optional[Dict[str, T]]: """Generic backtracking solver for any CSP.""" return backtrack({}, csp) def backtrack( assignment: Dict[str, T], csp: CSP[T] ) -> Optional[Dict[str, T]]: """Recursive backtracking with CSP structure.""" # Base case: all variables assigned = solution found if len(assignment) == len(csp.variables): return assignment.copy() # Return copy of solution # SELECT: Choose an unassigned variable variable = select_unassigned_variable(assignment, csp) # ORDER: Get domain values (possibly ordered by heuristics) values = order_domain_values(variable, assignment, csp) for value in values: # CHOOSE: Assign value to variable assignment[variable] = value # CHECK: Verify constraints if is_consistent(assignment, csp): # EXPLORE: Recurse on remaining problem result = backtrack(assignment, csp) if result is not None: return result # Solution found! # UNCHOOSE: Remove assignment for next attempt del assignment[variable] # BACKTRACK: No value worked, return failure return None def select_unassigned_variable( assignment: Dict[str, T], csp: CSP[T] ) -> str: """Select the next variable to assign.""" # Simple: return first unassigned variable # Better: use MRV (minimum remaining values) heuristic for v in csp.variables: if v not in assignment: return v raise ValueError("No unassigned variable") def order_domain_values( variable: str, assignment: Dict[str, T], csp: CSP[T] ) -> List[T]: """Order the domain values for a variable.""" # Simple: return domain in order # Better: use LCV (least constraining value) heuristic return csp.domains[variable][:] def is_consistent( assignment: Dict[str, T], csp: CSP[T] ) -> bool: """Check if current assignment violates any constraints.""" for constraint in csp.constraints: # Only check constraints where all variables are assigned all_assigned = all(v in assignment for v in constraint.variables) if all_assigned and not constraint.is_satisfied(assignment): return False return True6a:T82c,// Minimum Remaining Values (MRV) Variable Ordering function selectByMRV( assignment: Map, csp: CSP, domains: Map // 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( variable: string, assignment: Map, csp: CSP, domains: Map ): 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); }6b:T457,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.43:["$","$L62",null,{"owner":"anonymous","state":{"mutations":[],"queries":[{"dehydratedAt":1792306377965,"state":{"data":{"json":{"id":"seed_2b4f727f6d5b4c3c00d2b73d9875102b","slug":"constraint-satisfaction-pruning","category":"Data Structures & Algorithms","topic":"Constraint Satisfaction & Pruning","title":"Constraint Satisfaction & Pruning","description":"Master the art of optimizing backtracking through constraint satisfaction frameworks, powerful pruning techniques, forward checking, and arc consistency. Learn to transform exponential search spaces into tractable problems by eliminating dead ends before they're explored.","difficulty":"ADVANCED","estimatedMinutes":90,"pages":[{"id":"seed_3c474c7449471d9650e780c51a0de4fa","title":"General Constraint Satisfaction Framework","order":0,"content":[{"id":"opening-hook","title":"When Problems Become Puzzles","content":[{"data":{"content":"$63"},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"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.","variant":"info"},"type":"callout"}]},{"id":"what-is-csp","title":"What Is a Constraint Satisfaction Problem?","content":[{"data":{"content":"$64"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Power of Declarative Modeling","content":"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.","variant":"note"},"type":"callout"},{"data":{"content":"**Constraint Types:**\n\nConstraints come in many forms, each with different properties that affect solving strategies:\n\n**Unary Constraints:** Restrict a single variable's values. Example: \"Variable X₁ cannot be 5\" reduces X₁'s domain.\n\n**Binary Constraints:** Restrict pairs of variables. Example: \"X₁ ≠ X₂\" (different values) or \"X₁ < X₂\" (ordering). Binary constraints are the most common and well-studied.\n\n**Higher-Order Constraints (n-ary):** Restrict three or more variables simultaneously. Example: \"All of X₁, X₂, X₃ must be different\" (an all-different constraint).\n\n**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."},"type":"text"},{"data":{"rows":[["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"]],"caption":"Common Constraint Types in CSP Modeling","headers":["Constraint Type","Variables Involved","Example","Typical Usage"]},"type":"table"}],"titleType":"number","titleNumber":1},{"id":"constraint-graph","title":"The Constraint Graph: Visualizing Problem Structure","content":[{"data":{"content":"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.\n\n**For binary CSPs:**\n- Each variable becomes a **node**\n- Each binary constraint becomes an **edge** connecting the constrained variables\n- The graph structure reveals dependencies and potential solution strategies\n\n**Example: Map Coloring**\n\nConsider coloring a map of Australia with three colors (Red, Green, Blue) such that no adjacent regions share a color:\n\n- Variables: WA (Western Australia), NT (Northern Territory), SA (South Australia), Q (Queensland), NSW (New South Wales), V (Victoria), T (Tasmania)\n- Domains: {R, G, B} for each variable\n- Constraints: WA ≠ NT, WA ≠ SA, NT ≠ SA, NT ≠ Q, SA ≠ Q, SA ≠ NSW, SA ≠ V, Q ≠ NSW, NSW ≠ V\n\nThe constraint graph mirrors the geographical adjacency graph—each edge represents a shared border."},"type":"text"},{"data":{"fileName":"Map Coloring CSP Structure","languages":[{"code":"$65","label":"TypeScript","value":"typescript"},{"code":"$66","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"**Why Graph Structure Matters:**\n\nThe constraint graph reveals crucial information about problem difficulty and solution strategies:\n\n**Connectivity:** Disconnected components can be solved independently and solutions combined.\n\n**Density:** Sparse graphs (few constraints) have more solutions; dense graphs are more constrained and often harder.\n\n**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.\n\n**Cliques:** Highly connected subgraphs indicate tightly coupled variables that must be carefully coordinated.\n\nUnderstanding 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."},"type":"text"}],"titleType":"number","titleNumber":2},{"id":"csp-generalization","title":"CSP as a Universal Problem Language","content":[{"data":{"content":"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.\n\nLet's see how classic problems map to the CSP framework:"},"type":"text"},{"data":{"items":["**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."],"title":{"icon":"Target","text":"Classic Problems as CSPs","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"fileName":"N-Queens as CSP","languages":[{"code":"$67","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"icon":"Lightbulb","title":"Modeling is Key","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"csp-backtracking-connection","title":"The Deep Connection to Backtracking","content":[{"data":{"content":"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.\n\n**Standard Backtracking as CSP Solving:**\n\nThe backtracking template we've studied—choose, explore, unchoose—maps directly to CSP operations:\n\n1. **Choose:** Select an unassigned variable and assign it a value from its domain\n2. **Check:** Verify all constraints involving the newly assigned variable\n3. **Explore:** Recursively solve the remaining, smaller CSP\n4. **Unchoose:** If exploration fails, remove the assignment and try another value\n5. **Backtrack:** If no values work, return failure and let the caller try different earlier choices\n\nThis is exactly what backtracking does, just expressed in CSP vocabulary."},"type":"text"},{"data":{"fileName":"Generic CSP Backtracking Solver","languages":[{"code":"$68","label":"TypeScript","value":"typescript"},{"code":"$69","label":"Python","value":"python"}]},"type":"code"},{"data":{"content":"**The Search Tree Perspective:**\n\nEvery CSP defines a **search tree** that backtracking explores:\n\n- **Root:** Empty assignment (no variables assigned)\n- **Nodes:** Partial assignments (some variables assigned)\n- **Edges:** Extending an assignment with one more variable-value pair\n- **Leaves:** Complete assignments (all variables assigned) or failures (constraint violated)\n- **Solutions:** Complete assignments where all constraints are satisfied\n\nThe 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:\n\n$$\\text{Search space} = \\prod_{i=1}^{n} |D_i|$$\n\nFor 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."},"type":"text"},{"data":{"icon":"AlertCircle","title":"The Exponential Challenge","content":"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.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"ordering-heuristics","title":"Variable and Value Ordering Heuristics","content":[{"data":{"content":"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.\n\n**Variable Ordering: Which Variable to Assign Next?**"},"type":"text"},{"data":{"items":["**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."],"title":"Variable Ordering Heuristics","variant":"glass"},"type":"list"},{"data":{"content":"**Value Ordering: Which Value to Try First?**"},"type":"text"},{"data":{"items":["**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."],"title":"Value Ordering Heuristics","variant":"glass"},"type":"list"},{"data":{"fileName":"MRV and LCV Heuristics","languages":[{"code":"$6a","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"icon":"Lightbulb","title":"Why Opposite Strategies?","content":"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.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":5},{"id":"consistency-preview","title":"Consistency and Propagation: A Preview","content":[{"data":{"content":"$6b"},"type":"text"},{"data":{"left":[{"data":{"items":["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"],"title":{"icon":"XCircle","text":"Without Propagation","type":"icon","color":"destructive","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["Assign variable, propagate implications","Immediately reduce other domains","Empty domain = early failure detection","Vast pruning of search space","Constraint violations detected early"],"title":{"icon":"CheckCircle","text":"With Propagation","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"content":"**Example: Sudoku with Arc Consistency**\n\nConsider a Sudoku where a cell has candidates {1, 2, 5}. If through propagation we discover:\n- The 1 in this cell's row is forced elsewhere\n- The 5 in this cell's column is forced elsewhere\n\nWe 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.\n\nPropagation 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.\n\nIn 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."},"type":"text"}],"titleType":"number","titleNumber":6},{"id":"real-world-applications","title":"Real-World CSP Applications","content":[{"data":{"content":"The CSP framework isn't just academic theory—it powers countless real-world systems. Understanding CSPs opens doors to solving practical problems across industries."},"type":"text"},{"data":{"rows":[["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"]],"caption":"CSP Applications Across Industries","headers":["Domain","Problem","Variables","Constraints"]},"type":"table"},{"data":{"icon":"Zap","title":"Industry Impact","content":"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.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary-path-forward","title":"Summary: The CSP Framework","content":[{"data":{"content":"We've established the theoretical and practical foundation for understanding constraint satisfaction problems. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**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."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**What's Next:**\n\nNow 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."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"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.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_4c6dd593013eb1154467aeddb9390406","title":"Pruning Techniques to Reduce Search","order":1,"content":null,"isLocked":true},{"id":"seed_86c04caad114233d27e73ea946a4ec6d","title":"Forward Checking (Conceptual)","order":2,"content":null,"isLocked":true},{"id":"seed_415fb021430ca742e9971b8cb789f2fb","title":"Arc Consistency (Conceptual)","order":3,"content":null,"isLocked":true}]}},"dataUpdateCount":1,"dataUpdatedAt":1792306377964,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getModule"],{"input":{"slug":"constraint-satisfaction-pruning"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getModule\"],{\"input\":{\"slug\":\"constraint-satisfaction-pruning\"},\"type\":\"query\"}]"},{"dehydratedAt":1792306377965,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792306377963,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["learningContent","getProgress"],{"input":{"moduleId":"seed_2b4f727f6d5b4c3c00d2b73d9875102b"},"type":"query"}],"queryHash":"[[\"learningContent\",\"getProgress\"],{\"input\":{\"moduleId\":\"seed_2b4f727f6d5b4c3c00d2b73d9875102b\"},\"type\":\"query\"}]"},{"dehydratedAt":1792306377965,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792306377963,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","get"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_4c6dd593013eb1154467aeddb9390406"},"type":"query"}],"queryHash":"[[\"feedback\",\"get\"],{\"input\":{\"contentId\":\"seed_4c6dd593013eb1154467aeddb9390406\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792306377965,"state":{"data":{"json":null},"dataUpdateCount":1,"dataUpdatedAt":1792306377963,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["feedback","getUserLike"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_4c6dd593013eb1154467aeddb9390406"},"type":"query"}],"queryHash":"[[\"feedback\",\"getUserLike\"],{\"input\":{\"contentId\":\"seed_4c6dd593013eb1154467aeddb9390406\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792306377965,"state":{"data":{"json":[]},"dataUpdateCount":1,"dataUpdatedAt":1792306377963,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"success","fetchStatus":"idle"},"queryKey":[["highlights","getHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_4c6dd593013eb1154467aeddb9390406"},"type":"query"}],"queryHash":"[[\"highlights\",\"getHighlights\"],{\"input\":{\"contentId\":\"seed_4c6dd593013eb1154467aeddb9390406\",\"contentType\":\"LEARNING_PAGE\"},\"type\":\"query\"}]"},{"dehydratedAt":1792306377965,"state":{"data":"$undefined","dataUpdateCount":0,"dataUpdatedAt":0,"error":null,"errorUpdateCount":0,"errorUpdatedAt":0,"fetchFailureCount":0,"fetchFailureReason":null,"fetchMeta":null,"isInvalidated":false,"status":"pending","fetchStatus":"fetching"},"queryKey":[["highlights","getPopularHighlights"],{"input":{"contentType":"LEARNING_PAGE","contentId":"seed_4c6dd593013eb1154467aeddb9390406","minCount":2},"type":"query"}],"queryHash":"[[\"highlights\",\"getPopularHighlights\"],{\"input\":{\"contentId\":\"seed_4c6dd593013eb1154467aeddb9390406\",\"contentType\":\"LEARNING_PAGE\",\"minCount\":2},\"type\":\"query\"}]","promise":"$@6c"}]},"children":"$L6d"}]