Constraint Satisfaction

A constraint satisfaction problem (CSP) is a formal model defined by three elements: a set of variables, a domain of possible values for each variable, and a set of constraints that limit which combinations of values are allowed. A solution is an assignment of a value to each variable, taken from its domain, that satisfies all the constraints at once.

Examples

Many disparate problems share this structure, which is why they can be solved with the same algorithms. In map coloring, the variables are the regions, the domain is the colors and the constraint is that two neighboring regions not share a color. Sudoku, the N-queens problem or the drawing up of schedules are also constraint satisfaction problems.

How they are solved

The base algorithm is backtracking search: it assigns values to the variables one by one and, when a partial assignment violates a constraint, it undoes the last one and tries another. It is combined with constraint propagation, which prunes impossible values before continuing; the classic technique is arc consistency (the AC-3 algorithm). And with ordering heuristics, such as choosing first the variable with the fewest remaining legal values, or the value that least constrains the others.

Satisfaction versus optimization

Two goals are worth distinguishing. A satisfaction CSP looks for any assignment that meets all the constraints, or to determine that none exists: all valid solutions are equally good. A constrained optimization problem adds an objective function and looks for the best solution according to it. And when the constraints cannot all be met at once, the MAX-CSP variant looks for the assignment that satisfies the greatest possible number.