Constraint Satisfaction Problems (CSP): Concept — Beginner-Friendly Notes
1. What Is a CSP (different view of search)
Instead of states with paths, CSP sees a problem as:
- Variables (each discrete domain )
- Domains — possible values per variable (e.g., colours {R,G,B})
- Constraints — rules that forbid certain combos (e.g., adjacent regions must differ)
Goal: assign every variable a value that satisfies all constraints — path doesn't matter, only final assignment.
Search (Module 2A) cares about path; CSP cares about assignment that obeys constraints.
2. Classic Examples
| Problem | Variables | Domains | Constraints |
|---|---|---|---|
| Map colouring (India states) | Each state | {R,G,B} | Neighbours differ |
| 8-Queens | Each queen (column) | Rows 1-8 | No two attack each other |
| Sudoku | 81 cells | 1-9 | Row/col/box all-different |
| Timetable | Slots | Rooms/teachers | No clash |
3. Why CSP Formulation Helps
- Exposes structure — constraints are local, so we can use generic algorithms that exploit that.
- Same backtracking / propagation works for any CSP — you don't hand-craft search.
- Real industry problems are CSP-like: scheduling, config, rostering.
4. Types of Constraints
- Unary: one variable (e.g., $X1
eq red$) - Binary: two variables (e.g., $Xi
eq Xj$) — most common, forms constraint graph (nodes=variables, edges=constraints). - Higher-order / global: all-different, e.g., sudoku row.
5. What You Need Before Solving (next topic)
Solving naively = brute force (pick values, test constraints). CSP algorithms do better:
- Backtracking (depth-first assignment + check)
- Constraint propagation (forward checking, arc consistency) — prune domains early
- Ordering heuristics — which variable/value to try first (MRV, etc.)
6. One-Line Summary
A CSP specifies variables with domains and constraints on assignments, aiming for a consistent complete assignment, providing a structured, domain-independent way to model combinatorial problems like colouring, scheduling and Sudoku.
7. Quick Self-Check
- Model graph colouring of a triangle with 2 colours as CSP — is it satisfiable?
- Name variables, domains, constraints for 8-queens.