What Is a Constraint Satisfaction Problem?

Constraint satisfaction problems (CSPs) are mathematical problems defined as a set of objects whose state must satisfy one or more constraints.

For example:

• Map coloring problems — Assign colors to regions (US states, for instance) on a map such that no adjacent regions have the same color.
• Logical puzzles such as Sudoku — Complete a grid by entering digits 1 through 9 in each square such that each digit appears once and only once in each column, row, or subgrid.
• Traveling salesman problem — Plan the most efficient route through a series of cities so that each is visited once and only once.

In industry, problems of scheduling and resource allocation can be formulated as constraint satisfaction problems.