5.1 What is a CSP?
A Constraint Satisfaction Problem is a type of problem where:
- The solution must satisfy constraints (rules).
- You don’t need to search through all paths or actions — just find values for variables.
CSP = Find valid values
5.2 Components of a CSP
| Component | Description | Example: Map Coloring |
|---|---|---|
| Variables | The items to assign values to | Regions: A, B, C |
| Domains | Allowed values for each variable | Colors: Red, Green, Blue |
| Constraints | Rules that limit how variables can be assigned | Adjacent regions ≠ same color |
5.3 Types of Constraints
| Type | Description | Example |
|---|---|---|
| Unary | Applies to a single variable | A ≠ Red |
| Binary | Applies between two variables | A ≠ B |
| Higher-Order | Involves 3 or more variables in a rule | A ≠ B ≠ C |
| Global Constraints | Apply to large sets, often patterns | "AllDifferent" in Sudoku |
5.4 Solving CSPs: Techniques
Backtracking Search
Try assigning values one by one, and backtrack when a constraint is violated.
Recursive, depth-first search approach.
Forward Checking
After assigning a variable, look ahead and remove values from other variable domains that are no longer valid.
Constraint Propagation
Propagate changes to narrow down possible values in all related variables.
5.5 Frequently Asked Exam Questions
- Define CSP. Explain components with examples.
- What is constraint propagation? How does it differ from forward checking?
- Solve the following map coloring problem with a constraint graph.
- Define arc consistency. Explain AC-3 with a suitable example.
- Compare backtracking, forward checking, and constraint propagation.