# AIMA: Constraint Satisfaction Problems

> Source: https://ollybritton.com/notes/textbooks/ai-a-modern-approach/problem-solving/constraint-satisfaction-problems/ · Updated: 2021-04-04 · Tags: aima

## Flashcards
##### What sort of representation do CSPs use in comparison to the atomic representation used by search algorithms??
A factored representation.

##### What is the domain of a variable in a CSP??
The set of the variables it can take on.

##### What are the constraints in a CSP??
Expressions that limit what values a variable can take on.

##### What are inference techniques in CSPs??
Using constraints to rule out certain variable assignments.

##### What is the minimum-remaining-values heuristic??
Choosing variables with the smallest domain to assign values to next.

##### What is the degree heuristic for CSPs??
Choosing variables involved in the largest number of constraints to assign values to next.

##### What is the least-constraining-value heuristic??
Choosing values for variables that have the smallest affect on constraining other variables.

##### What is conflict-directed backjumping??
Backtracking to the source of conflicts rather than the last modification made.

##### What is constraint learning in CSPs??
Recording conflicts made as a CSP is searched for solutions to avoid future conflicts.

##### What is a good heuristic to use for local search on CSPs??
min-conflicts

##### Why is it a good idea to turn CSPs into trees??
Because trees can be solved in polynomial time.

##### What are the two ways of transforming a normal graph CSP into a tree??
* Cutset conditioning
* Tree decomposition

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt