A standard Constraint Satisfaction Problem (CSP) is a finite-choices decision problem where one is given a fixed set of decisions to make. Each decision involves choosing among a fixed set of options. Each constraint restricts the combination of choices that can be taken simultaneously. The task is to make all the decisions such that all the constraints are satisfied. Many real life problems, such as planning, scheduling and timetabling can be formalised as constraint satisfaction problems. Very efficient algorithms have been developed for solving constraint satisfaction problems (by exploiting their characteristics). Constraint programming is a multi-million Dollars business.
In CSPs where some solutions are better than others, one may be asked to find the optimal solution according to a specific objective function. In CSPs where no solutions exist, one may be asked to find the "best" near-solutions according to a specific objective function (e.g. to violate the least number of constraints).
Some of the fundamental topics in constraint satisfaction include:
To learn more about the field, follow a longer tutorial, or E.P.K. Tsang, Foundations of Constraint Satisfaction, Academic Press, London, 1993, E.C. Freuder & A. Mackworth (ed.), Constraint-based Reasoning, MIT Press, 1994, Journal of CONSTRAINTS and research articles in recent journals and conference proceedings. To get to know more about other researchers in the field, visit other sites in the well organized Constraint Archives following our Links to other WWW Pages.
(Download and install the 8-Queens Demo to see an example constraint satisfaction problem and constraint techniques in action.)
This page is maintained by:
Constraint Satisfaction Home Page (http://cswww.essex.ac.uk/CSP)