Constraint Satisfaction Problem(CSP)

A Constraint Satisfaction Problem consists of 3 components

1. A set of variables.
2. A set of values for each of the variables.
3. A set of constraints between various collections of variables.

We must find a value for each of the variables that satisfies all of the constraints.

Search Space

The search space depends on variable orderings.

Example

Given the following constraint network:

• Variables: X, Y, Z
• Domains: Dz={5,2}, Dx={2,4}, Dy={5,2}
• Constraints: Rzx = Z divides X, Rzy = Z divides Y

With the ordering d={Z, X, Y}, the search space explored is:

With the ordering d={X, Y, Z}, the search space explored is: