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.

Glossary:

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s