A little bit of theory

We are talking about Constraint Satisfaction Problem .

A CSP $\mathcal{P}$ is a triple $\left<\mathcal{X},\mathcal{D},\mathcal{C}\right>$ where:

  • $\mathcal{X} = \{X_1, \ldots, X_n\}$ is a set of variables,
  • $\mathcal{D}$ is a function associating a domain to each variable,
  • $\mathcal{C}$ is a set of constraints.

It can be turn into a COP quite easily

Let’s consider the following CSP $\mathcal{P}$:

  • $\mathcal{X} = \{X_1, X_2, X_3\}$
  • $\mathcal{D} = \{D(X_1)=D(X_2)=[1,2], D(X_3)=[1,3]\}$
  • $\mathcal{C} = \{X_1\leq X_2,X_2\leq X_3,AtMost(1,[X_1, X_2, X_3],2)\}$

A constraint defines a relation between variables.

It is said to be satisfied if :

  • its variables are instantiated to a single value*
  • and the relation holds


*: $x_{i_k} \in \mathcal{D}(X_{i_k})$

In $\mathcal{P}$, the constraint $AtMost(1,[X_1, X_2, X_3],2)$ holds iff at most 1 variable among $X_1, X_2, X_3$ is assigned to the value 2.

  • $(1,1,1)$ and $(1,2,3)$ satisfy the constraint,
  • $(2,2,1)$ does not.

The constraints can be defined in intension or in extension .

For $X_1$, $X_2$ on domains $\{1,2\}$:

  • intension:
    • expression in a higher level language
    • e.g., $X_1+X_2\le3$
  • extension:
    • allowed combinations
    • e.g., ${(1,1),(1,2),(2,1)}$

Less formally

What we know about a variable is that :

  • it takes its values from a domain *, e.g., {1,2,3,5},
  • it is linked to other variables using constraints ,
  • and it must be instantiated in a solution .


*: discrete domain in our case.

On the other hand, a constraint :

  • defines a contract between its variables,
  • must be satisfied in every solutions,
  • and is more than just a checker.

Choose your favourite programming language

(I chose Python)

and let’s get started