from
The Free On-line Dictionary of Computing (8 July 2008)
constraint satisfaction
<application> The process of assigning values to variables
while meeting certain requirements or "{constraints}". For
example, in {graph colouring}, a node is a variable, the
colour assigned to it is its value and a link between two
nodes represents the constraint that those two nodes must not
be assigned the same colour. In {scheduling}, constraints
apply to such variables as the starting and ending times for
tasks.
The {Simplex} method is one well known technique for solving
numerical constraints.
The search difficulty of constraint satisfaction problems can
be determined on average from knowledge of easily computed
structural properties of the problems. In fact, hard
instances of {NP-complete} problems are concentrated near an
abrupt transition between under- and over-constrained
problems. This transition is analogous to phase transitions
in physical systems and offers a way to estimate the likely
difficulty of a constraint problem before attempting to solve
it with search.
Phase transitions in search
(ftp://parcftp.xerox.com/pub/dynamics/constraints.html) (Tad
Hogg, {XEROX PARC}).
(1995-02-15)