Constraint Satisfaction Problems: Solving Complex Constraints

Introduction

Constraint satisfaction problems (CSPs) are a fundamental class of computational problems where we must find assignments of values to variables that satisfy a set of constraints. CSPs appear everywhere: scheduling, planning, configuration, puzzle solving, and many other domains. This article explores CSP formulation, solution techniques, and practical applications.

Historical Context

Constraint satisfaction emerged as a research area in the 1970s and 1980s. Early work focused on backtracking algorithms and constraint propagation. The field has evolved to include sophisticated techniques like arc consistency, constraint learning, and hybrid approaches combining CSP with SAT and optimization. Modern CSP solvers handle complex real-world problems in scheduling, planning, and configuration.

Problem Definition

Constraint Satisfaction Problem

Definition: A CSP consists of:

Variables: X = {x₁, x₂, …, xₙ}
Domains: D = {D₁, D₂, …, Dₙ} where Dᵢ is domain of xᵢ
Constraints: C = {c₁, c₂, …, cₘ} where each cᵢ restricts values

Goal: Find assignment of values to variables satisfying all constraints

Solution: Assignment σ: X → ∪D such that all constraints are satisfied

Constraint Types

Unary Constraint: Restricts single variable

Example: x > 5

Binary Constraint: Restricts two variables

Example: x < y

Higher-Arity Constraint: Restricts multiple variables

Example: x + y + z = 10

Example: Map Coloring

Problem: Color map with 4 colors such that adjacent regions have different colors

Variables: {WA, NT, Q, NSW, V, SA, T} Domains: Each variable ∈ {red, green, blue, yellow} Constraints:

WA ≠ NT
WA ≠ SA
NT ≠ Q
NT ≠ SA
Q ≠ NSW
Q ≠ SA
NSW ≠ V
NSW ≠ SA
V ≠ SA

Solution Techniques

Backtracking Search

Algorithm:

Algorithm Backtrack(assignment, csp)
1. If assignment is complete, return assignment
2. Select unassigned variable x
3. For each value v in domain of x:
   a. If v is consistent with assignment:
      i. Add x = v to assignment
      ii. Result = Backtrack(assignment, csp)
      iii. If result ≠ failure, return result
      iv. Remove x = v from assignment
4. Return failure

Advantages: Complete, simple Disadvantage: Can be very slow (exponential)

Constraint Propagation

Idea: Use constraints to reduce domains before search

Benefit: Reduces search space

Arc Consistency

Definition: Arc (xᵢ, xⱼ) is consistent if for every value in Dᵢ, there exists value in Dⱼ satisfying constraint

Algorithm (AC-3):

Algorithm AC-3(csp)
1. Queue = all arcs in csp
2. While queue not empty:
   a. (xᵢ, xⱼ) = dequeue()
   b. If Revise(xᵢ, xⱼ):
      i. If Dᵢ is empty, return failure
      ii. For each neighbor xₖ of xᵢ:
          - Enqueue (xₖ, xᵢ)
3. Return csp

Algorithm Revise(xᵢ, xⱼ)
1. Revised = false
2. For each value v in Dᵢ:
   a. If no value w in Dⱼ satisfies constraint(xᵢ=v, xⱼ=w):
      i. Delete v from Dᵢ
      ii. Revised = true
3. Return revised

Benefit: Reduces domains significantly

Path Consistency

Idea: Extend arc consistency to paths of length 3

Benefit: Stronger consistency than arc consistency

Cost: More expensive to compute

Variable and Value Ordering

Variable Ordering

Minimum Remaining Values (MRV):

Choose variable with smallest domain
Benefit: Fails fast if no solution

Degree Heuristic:

Choose variable involved in most constraints
Benefit: Reduces future choices

Combination: Use degree as tiebreaker for MRV

Value Ordering

Least Constraining Value (LCV):

Choose value that rules out fewest values in neighbors
Benefit: Leaves options open

Benefit: Often finds solutions faster

Constraint Learning

Idea: Learn constraints from conflicts

Example:

If assignment {x=1, y=2, z=3} violates constraint,
Learn: ¬(x=1 ∧ y=2 ∧ z=3)

Benefit: Avoids similar conflicts

Backjumping

Idea: Jump back to relevant variable instead of immediate predecessor

Benefit: Avoids redundant search

Practical Example: Sudoku

Problem: Fill 9×9 grid with digits 1-9 such that:

Each row contains 1-9
Each column contains 1-9
Each 3×3 box contains 1-9

Variables: 81 cells Domains: Each cell ∈ {1,2,…,9} Constraints: Row, column, box constraints

Solution Approach:

Apply constraint propagation (arc consistency)
Use backtracking with MRV heuristic
Learn constraints from conflicts

CSP Solvers

Constraint Programming Languages

Prolog: Logic programming with constraints MiniZinc: High-level constraint modeling language Choco: Java constraint solver OR-Tools: Google’s optimization toolkit

Hybrid Approaches

CSP + SAT: Encode CSP as SAT, use SAT solver CSP + ILP: Encode CSP as integer linear program CSP + Local Search: Combine systematic search with local optimization

Applications

Scheduling

Problem: Schedule tasks respecting time and resource constraints Example: University course scheduling

Planning

Problem: Find sequence of actions achieving goal Example: Robot planning

Configuration

Problem: Configure system respecting constraints Example: Computer system configuration

Puzzle Solving

Problem: Solve logic puzzles Example: Sudoku, N-queens, crosswords

Glossary

Arc Consistency: Consistency between pairs of variables

Backjumping: Jump back to relevant variable

Backtracking: Systematic search with backtracking

Constraint: Restriction on variable values

Constraint Propagation: Use constraints to reduce domains

CSP: Constraint satisfaction problem

Domain: Set of possible values for variable

MRV: Minimum remaining values heuristic

Path Consistency: Consistency along paths

Variable: Unknown to be assigned

Practice Problems

Problem 1: Formulate N-queens problem as CSP.

Solution:

Variables: {q₁, q₂, ..., qₙ} (position of queen in each row)
Domains: Each qᵢ ∈ {1, 2, ..., n}
Constraints:
- qᵢ ≠ qⱼ (no two queens in same column)
- |qᵢ - qⱼ| ≠ |i - j| (no two queens on same diagonal)

Problem 2: Apply AC-3 to map coloring problem.

Solution: Iteratively remove values from domains that don’t have consistent values in neighboring regions until no more changes occur.

Problem 3: Explain how MRV heuristic helps in CSP solving.

Solution: MRV chooses variable with smallest domain, which fails fast if no solution exists. This prunes the search tree early, reducing overall search time.

Constraint Satisfaction: https://en.wikipedia.org/wiki/Constraint_satisfaction_problem
Arc Consistency: https://en.wikipedia.org/wiki/Arc_consistency
Backtracking: https://en.wikipedia.org/wiki/Backtracking
MiniZinc: https://www.minizinc.org/
Choco: https://choco-solver.org/
OR-Tools: https://developers.google.com/optimization
Constraint Programming: https://en.wikipedia.org/wiki/Constraint_programming
Scheduling: https://en.wikipedia.org/wiki/Scheduling_(computing)
Planning: https://en.wikipedia.org/wiki/Automated_planning_and_scheduling
SAT Solvers: https://en.wikipedia.org/wiki/SAT_solver
Integer Linear Programming: https://en.wikipedia.org/wiki/Integer_programming
Local Search: https://en.wikipedia.org/wiki/Local_search_(optimization)
Optimization: https://en.wikipedia.org/wiki/Mathematical_optimization
Puzzle Solving: https://en.wikipedia.org/wiki/Puzzle
Formal Methods: https://plato.stanford.edu/entries/formal-methods/

Conclusion

Constraint satisfaction problems represent a powerful framework for modeling and solving complex real-world problems. By combining systematic search with constraint propagation and intelligent heuristics, CSP solvers can handle problems with thousands of variables and constraints.

Understanding CSP techniques is essential for anyone working in scheduling, planning, configuration, or optimization. The combination of theoretical foundations and practical algorithms makes CSP a valuable tool in computational problem-solving.