Constraint satisfaction problems (CSPs) are mathematical problems defined as a set of objects whose state must satisfy one or more constraints.
- 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.