Lernzettel: Constraint Satisfaction Problems (CSP)
Methods of AI — SoSe 2026 · 1-page exam sheet
For more depth: Constraint Satisfaction Problems (full reference with all algorithms, visualisations, deep explanations) · quiz_csp_30-04-26 (15 practice questions)
Core Ideas
- A CSP is defined by variables, domains, and constraints. Goal: find a complete assignment satisfying all constraints.
- Unlike search: states have internal structure (variable assignments) that the algorithm exploits.
- Three solution strategies: naive (generate & test), backtracking search, local search.
- Consistency preprocessing can dramatically shrink the search space before search even begins.
Mini-glossary
| Term | Meaning |
|---|---|
| Variable Xᵢ | a slot to fill |
| Domain D(Xᵢ) | values Xᵢ may take (shrinks during search) |
| Constraint | unary / binary / n-ary relation restricting allowed combinations |
| Partial assignment | only some variables have values |
| Complete assignment | every variable has a value |
| Consistent assignment | no constraint currently violated (can be partial) |
| Solution | complete AND consistent |
| Consistent CSP | at least one solution exists |
| MRV | pick next variable with smallest domain (fail-fast) |
| LCV | pick next value that rules out fewest neighbour options (fail-slow) |
| Forward Checking | after assigning X=v, remove v from unassigned neighbour domains |
| AC-3 | arc-consistency preprocessing — propagate “every value has a supporter” |
⚠️ “Consistent” has two meanings: about an assignment (no current violation) vs. about a CSP (a solution exists). Context disambiguates.
⭐ Full glossary with examples → Glossary — important CSP vocabulary ⭐
Formulas & Notation
| Symbol | Meaning |
|---|---|
| Xᵢ | Variable i |
| Dᵢ | Domain of variable i |
| R | Set of constraints |
| AC-3 complexity | O(cd³) |
| MRV | Minimum Remaining Values heuristic |
| LCV | Least Constraining Value heuristic |
Common Exam Traps ⚠️
- AC-3 removes values from domains — it changes the CSP structure, not just tests it.
- Arc consistency ≠ path consistency: 2-consistent doesn’t mean 3-consistent.
- LCV is for value ordering (keep options open); MRV is for variable ordering (fail early). Different goals, don’t mix.
- If local search finds global optimum on CSP objective → CSP is consistent. If local optimum with violations → you can’t tell.
- Strong k-consistency means j-consistent for all j ≤ k. Regular k-consistency only guarantees at level k.
- Backtracking is not local search — it uses partial assignments; local search uses complete (possibly invalid) assignments.
Quick Comparison Table
| Approach | Assignment type | Completeness | When to use |
|---|---|---|---|
| Backtracking | Partial | Complete | General CSPs |
| Local Search | Complete (may violate) | Incomplete | Large CSPs, soft constraints OK |
| AC-3 preprocessing | N/A | — | Before any search (reduce domains) |
| MRV | Variable selection heuristic | — | Always good to combine with BT |
Full pros/cons comparison of all 9 algorithms → Algorithm comparison table — pros & cons
Related Q&A & Notes
Practice quiz
- quiz_csp_30-04-26 — 15 questions (7 text + 8 graph-based)
Targeted exam questions in Questions for Methods of AI
- Q17–29 (basic CSP, arc consistency, backtracking, heuristics) · Q88–89 (CSP components, Node/Arc consistency) · Q110–113 (deep / exam-trap: AC-3 complexity O(c·d³), MRV vs. Degree as tie-breaker, MRV vs. LCV non-conflict, RCC-8)
Atomic notes
See also
Tags: methods-of-ai lernzettel
Full reference: Constraint Satisfaction Problems
Quiz: quiz_csp_30-04-26
Superlink: Methods of AI Lecture
Questions hub: Questions for Methods of AI
Created: 30/04/26