Constraint Satisfaction Problems

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.

Leave a Reply

%d bloggers like this: