R68  
Constraint Satisfaction
Rina Dechter (dechter@ics.uci.edu)

Abstract A constraint satisfaction problem (csp) defined over a constraint network consists of a finite set of variables, each associated with a domain of values, and a set of constraints. A solution is an assignment of a value to each variable from its domain such that all the constraints are satisfied. Typical constraint satisfaction problems are to determine whether a solution exists, to find one or all solutions and to find an optimal solution relative to a given cost function. An example of a constraint satisfaction problem is the well known kcolorability... [ps] [pdf] 