Constraint Satisfaction Problem
A set of
Xi must take its value from Di.
D have to be a finite set of integers instead of a real-valued domain that would include an infinite number of real-values between two bounds.
- CSPs are a special kind of problem:
states defined by values of a fixed set of variables
goal test defined by constraints on variable values
Backtracking = depth-first search with one variable assigned per node
Variable ordering and value selection heuristics help significantly
Forward checking prevents assignments that guarantee later failure
Constraint propagation (e.g., arc consistency) does additional work to constrain values and detect inconsistencies
Iterative min-conflicts is usually effective in practice