Constraint satisfaction problem - Definition and Overview

Constraint-satisfaction problems or CSPs are mathematical problems where one must find states or objects in a system that satisfy a number of constraints or criteria. CSPs are the subject of intense research in both artificial intelligence and operations research. Many CSPs require a combination of heuristics and combinatorial search methods to solve in a reasonable time.

Examples of constraint-satisfaction problems:

• Eight queens puzzle
• Map-coloring problem

See also:

• Declarative programming
• Constraint programming

External links

• One very good text on the subject is Edward Tsang's Foundations of Constraint Satisfaction (http://www.cs.essex.ac.uk/CSP/edward/FCS.html).