Combines guessing with deduction.
Guesses can walk you through blind alleys, avoiding these blind alleys with dead ends is the main challenge.
P vs NP problem – It essentially asks whether every problem whose answer can be checked quickly by a computer can also be quickly solved by a computer.
Constraint solving has found most success with scheduling problems.
A search problem where we don’t care about the path but the goal itself.
Example: Map coloring problem
- No two adjacent states can have same color.
Pick the one with fewest remaining values to fill first.
Application: Paraphrasing with rhyming constraint to generate poetry.
For example in sudoku, variables are all the boxes in that 9*9 matrix and domain is the set of all possible values we can fill each variable with (0-9 in sudoku) and constraints are specific to that problem.