For a brief technical tutorial, click here.
Constraint satisfaction is about decision-making. It is about making a large number of decisions, satisfying complex constraints. Decision problems are found everywhere; rarely are they unconstrained. Therefore constraint satisfaction is ubiquitous. For example, an airline company has to assign aircraft and staff to serve each of its flights, meeting physical constraints and regulations. A factory has to schedule its machines and workers to produce different products at different times, meeting production constraints. A delivery company has to schedule its delivery teams to meet customers' demands and constraints.
The problem is difficult because there are many possible combinations in the decisions. This is called combinatorial explosion. This is a fundamental problem in computer science. Combinatorial explosion is the very problem that makes passwords difficult to crack. This is also the problem that gives computer scientists a lot to work on (without this problem, computers would have beaten human in chess long ago).
If a problem has a fixed number of decisions, and each of which is limited in its choices, then one can develop specialized, clever techniques to take advantage of these characteristics. Some of these techniques are based on the concept of constraint propagation. For example, if we have assign a pilot to serve flight F, then the same pilot cannot serve another flight that overlaps F in time. Simple though this idea might sound, powerful techniques can be derived from it. Other techniques involve heuristics to speed up the exploration of solutions.
To learn more about the field, take my module Constraint Satisfaction for Decision Making, or study E.P.K. Tsang, Foundations of Constraint Satisfaction, Academic Press, London, 1993.
