Constraint Satisfaction Problem
- Definition
- A Constraint Satisfaction Problem (CSP) asks for values of variables that satisfy all constraints simultaneously (like Sudoku). Picture setting variable values while checking many rules until everything is consistent. CSP techniques differ from optimization because they focus on feasibility rather than optimizing a numeric objective and often use search with pruning.
How does it work?
Constraint Satisfaction Problem methods manipulate symbols or rules: represent knowledge explicitly, and apply inference algorithms (forward/backward chaining, constraint propagation, search). Implementations focus on rule ordering, conflict resolution, and efficient indexing of facts.
Examples
- Exam timetabling — Assign exams to slots and rooms satisfying room capacity and conflict constraints.
- Sudoku solving — Express constraints and solve with backtracking for exact solutions.
- Resource allocation in scheduling — Enforce complex availability and precedence constraints in rostering.
Problems
- Combinatorial explosion of the search space for large problems
- Choosing effective variable/value ordering heuristics
- Detecting and encoding all real-world constraints correctly
- Backtracking search can be slow without good constraint propagation