On the other hand constraint propagation has been the core algorithm
used in solving a large class of problems termed constraint
satisfaction problems (CSP's).
Standard CSP's have a fixed finite number of problem variables, and
each variable has a finite set of possible values it can take (called
its domain).
The constraints between the variables can always be expressed as a set
of admissible combinations of values.
These constraints can be directly represented as relations in a
relational database, in which case each admissible combination is
a tuple of the relation.
CSP's have inspired a fascinating variety of research because
despite their simplicity they can be used to express - in a very
natural way - real, difficult, problems
.
One line of research has focussed on constraint propagation, showing how to propagate more and more information (forward checking, arc-consistency, path-consistency, k-consistency, relational consistency and so on). For example arc-consistency is achieved by reducing the domains of the problem variables until the remaining values are all supported; a value is supported if every constraint on the variable includes a tuple in which the variable takes this value and the other variables all take supported values.
Even if none of the arc-consistent domains are empty, this does not imply the CSP has a solution! To find a solution it is still necessary to try out specific values for the problem variables. Only if all the variables can be assigned a specific value, such that they all support each other, has a solution been found. One algorithm for solving CSP's, which has proved useful in practice, is to select a value for each variable in turn, but, after making each selection, to re-establish arc-consistency. Thus search is interleaved with constraint propagation. In this way the domains of the remaining values are reduced further and further until either one becomes empty, in which case some previous choice must be changed, or else the remaining domains contain only one value, in which case the problem is solved.
Another line of research has investigated the global shape of the problem. This shape can be viewed as a graph, where each variable is a node and each constraint an edge (or hyper-edge) in the graph. Tree-structured problems are relatively easy to solve, but research has also revealed a variety of ways of dealing with more awkward structures, by breaking down a problem into easier subproblems, whose results can be combined into a solution of the original problem. Picturesque names have been invented for these techniques such as ``perfect relaxation'' and ``hinge decomposition''.
More recently researchers have begun to explore the structure of the individual constraints. If the constraints belong to certain classes, propagation can be much more efficient - or it can even be used to find globally consistent solutions in polynomial time. Indeed there are quite nice sufficient conditions to distinguish between NP-complete problem classes and problem classes solvable with known polynomial algorithms.