Constraint satisfaction problems or CSPs are mathematical problems where one must find states or objects 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 be solved in a reasonable time.
Examples of constraint satisfaction problems:
- Eight queens puzzle
- Map coloring problem
- Boolean satisfiability
Examples of algorithms used for solving constraint satisfaction problems:
CSP classification Edit
Below are the main classification of Constraint Satisfaction Problem according to the University of York.
Scheduling problems are characterised by assigning start times to a series of tasks that have to be performed by some deadline with the possibility of precedence constraints between them. They are commonly modelled as a function from times to tasks. This description only covers a small subset of possible scheduling problems. Study of the full range of problems (with various resource and other constraints) is a subject in its own right.
These problems involve creating relationships between objects and labels (i.e. a collection of object label pairs) subject to additional constraints. These configurations can be represented as a relation or in some cases as a multiset of sets.
This class of problems involves assigning a single label to a number of objects (labels may be used zero or more times in the general case). The most common model is a total function.
These problems involve constructing a set of objects according to some constraints. A common goal is to maximise the size of the set of objects whilst ensuring all objects are compatible with each other. One difficulty with this class of problems is that th size of the decision variable may not be bounded.
Positioning problems involve arranging objects according spacial/geometric constraints. Typically all objects must lie within a boundary and objects are not permitted to overlap. These problems can be modelled as an assignment of co-ordinates to objects or as a grid, where each cell is taken up by part of an object.