Systematic Versus Stochastic Constraint Satisfaction
Eugene C. Freuder (ecf@cs.unh.edu), Rina Dechter (dechter@ics.uci.edu), Matthew L. Ginsberg (ginsberg@cs.uoregon.edu), Bart Selman (selman@research.att.com) & Edward Tsang (edward@essex.ac.uk)

Constraint satisfaction problems (CSPs) involve finding values for problem variables that satisfy restrictions on which combinations of values are allowed [Freuder and Mackworth, 1994; Tsang, 1993]. They have many applications, including planning and scheduling, design and configuration, vision and language, temporal and spatial reasoning. The map coloring problem is a simple example, where the problem variables correspond to countries, the values to colors, and the constraints specify that neighboring countries cannot have the same color.

  [ps] [pdf]