Constraint Satisfaction Problem (CSP) and Models

A Constraint Satisfaction Problem(CSP), is a triple < X, D, C > with:

• X is a set of variables { x₁,..., x_n}
• D = { D₁,..., D_n} is a set of associated domains for all x_i $\in$ X
• C is a set of constraints

A CSP M is called model for a problem P if every solution of P is also determined by the solutions to M.

The first two elements of the triple have a special meaning because they are the first thing we have to think about when modeling a constraint problem. These two sets X, D can be defined as the viewpoint of a problem, presented next.