Abstract
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.