Constraint Satisfaction Problem Formulation

Constraint satisfaction appear everywhere. With CSPs being ubiquitous, it is worth developing specialized techniques for solving them. Some powerful techniques have been developed, to exploit the characteristics of CSPs. If you want to make use of these techniques, you need to cast a problem as a CSP. This step is called problem formulation, or modelling.

Problem formulation is more an art than a science. There is no mechanical way to generate a CSP. But you can approach it by using a check list.

1. What are the variables?
2. What is the domain of each variable?
3. What are the constraints on the values that the variables can take?

Once you have formulated your CSP, you should be able to ignore the original specification when you solve the problem. You can check whether your formulation is correct by asking yourself:

1. Does each variable represent a decision?
2. Is a solution to the CSP that you have formulated an answer to the problem that is specified?
3. Does your formulation allow you to return all valid solutions to the problem that is specified?