Programmation par contraintes

Définition — Un problème de satisfaction de contraintes sur des domaines finis (ou CSP) est défini par un triplet ${\displaystyle ({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$  où:

• ${\displaystyle {\mathcal {X}}=\{x_{1},\dots ,x_{n}\}}$  est l'ensemble de variables du problème;
• ${\displaystyle {\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}}$  est l'ensemble des domaines des variables, c'est-à-dire que pour tout ${\displaystyle k\in [1;n]}$  on a ${\displaystyle x_{k}\in {\mathcal {D}}_{k}}$ ;
• ${\displaystyle {\mathcal {C}}=\{C_{1},\dots ,C_{m}\}}$  est un ensemble de contraintes. Une contrainte ${\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}$  est définie par l'ensemble ${\displaystyle {\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}}$  des variables sur lequel elle porte et la relation ${\displaystyle {\mathcal {R}}_{i}\subset {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}}$  qui définit l'ensemble des valeurs que peuvent prendre simultanément les variables de ${\displaystyle {\mathcal {X}}_{i}}$ :

Définition —  Une affectation ${\displaystyle {\mathcal {A}}}$  d'un CSP ${\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$  est définie par le couple ${\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}$  où:

• ${\displaystyle {\mathcal {X_{\mathcal {A}}}}\subset {\mathcal {X}}}$  est un sous-ensemble de variables;
• ${\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}}\}}$  est le tuple des valeurs prises par les variables affectées.

Propriété — Soit ${\displaystyle {\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})}$  une affectation (partielle ou totale) d'un CSP ${\displaystyle P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})}$ , et ${\displaystyle C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})}$  une contrainte de ${\displaystyle P}$  telle que ${\displaystyle {\mathcal {X}}_{i}\subset {\mathcal {X_{\mathcal {A}}}}}$ , l'affectation ${\displaystyle {\mathcal {A}}}$  satisfait la contrainte ${\displaystyle C_{i}}$  si et seulement si l'ensemble des valeurs ${\displaystyle {\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}}$  des variables sur lesquelles porte la contrainte ${\displaystyle C_{i}}$  appartient à ${\displaystyle {\mathcal {R}}_{i}}$ .

Définition — Une solution d'un CSP est une affectation totale qui satisfait l'ensemble des contraintes.