Definition — A constraint satisfaction problem on finite domains (or CSP) is defined by a triplet ${\displaystyle ({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$ where:

• ${\displaystyle {\mathcal {X}}=\{x_{1},\dots ,x_{n}\}}$ is the set of variables of the problem;
• ${\displaystyle {\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}}$ is the set of domains of the variables, i.e., for all ${\displaystyle k\in [1;n]}$ we have ${\displaystyle x_{k}\in {\mathcal {D}}_{k}}$;
• ${\displaystyle {\mathcal {C}}=\{C_{1},\dots ,C_{m}\}}$ is a set of constraints. A constraint ${\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}$ is defined by a set ${\displaystyle {\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}}$ of variables and a relation ${\displaystyle {\mathcal {R}}_{i}\subseteq {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}}$ that defines the set of values allowed simultaneously for the variables of ${\displaystyle {\mathcal {X}}_{i}}$.

Definition —  An assignment (or model) ${\displaystyle {\mathcal {A}}}$ of a CSP ${\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$ is defined by the couple ${\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}$ where:

• ${\displaystyle {\mathcal {X_{\mathcal {A}}}}\subseteq {\mathcal {X}}}$ is a subset of variable;
• ${\displaystyle {\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}}$ is the tuple of the values taken by the assigned variables.

Property — Given ${\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}$ an assignment (partial or total) of a CSP ${\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$, and ${\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}$ a constraint of ${\displaystyle P}$ such as ${\displaystyle {\mathcal {X}}_{i}\subseteq {\mathcal {X_{\mathcal {A}}}}}$, the assignment ${\displaystyle {\mathcal {A}}}$ satisfies the constraint ${\displaystyle C_{i}}$ if and only if all the values ${\displaystyle {\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}}$ of the variables of the constraint ${\displaystyle C_{i}}$ belongs to ${\displaystyle {\mathcal {R}}_{i}}$.

Definition — A solution of a CSP is a total assignment that satisfies all the constraints of the problem.