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