Constraint satisfaction problem

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

Examples of algorithms used in constraint-satisfaction problems:

• AC-3

See also:

• Declarative programming
• Constraint programming

External links

• One very good text on the subject is Edward Tsang's Foundations of Constraint Satisfaction.