Chapitre 12
Problèmes de satisfaction de
contraintes
"La programmation par contraintes est une des techniques qui se rapproche le plus du
Saint-Graal de la programmation : l'utilisateur définit le problème, l'ordinateur le résout"
Eugene Freuder.
12.1 Introduction
On modélise un problème de satisfaction de contraintes à l'aide de trois ensembles :
- un ensemble de variables,
- un ensemble de valeurs possibles pour chaque variable,
- un ensemble de contraintes qui relient les variables entre elles.
Une solution à un problème de satisfaction de contraintes consiste à trouver une valeur pour chaque variable de façon à ce que toutes les contraintes soient satisfaites. Les
contraintes sont des relations qui doivent être vérifiées sur les variables et les valeurs. Par
exemple, si x et y sont des variables du problème, x x y = 14 est une contrainte. Si x a
pour valeurs possibles 1,2,5 et que y a pour valeurs possibles 5,7, la solution unique au
problème est x = 2 et y = 7.
Dans ce chapitre nous montrons comment programmer des algorithmes simples de
programmation par contraintes. Il existe de nombreux solveurs de contraintes utilisant
des algorithmes bien plus évolués et plus efficaces que ceux que nous montrons, de même
qu'il existe des modélisations plus évoluées que celles que nous utilisons comme par
exemple pour le Sudoku [83].
Problèmes de satisfaction de
contraintes
"La programmation par contraintes est une des techniques qui se rapproche le plus du
Saint-Graal de la programmation : l'utilisateur définit le problème, l'ordinateur le résout"
Eugene Freuder.
12.1 Introduction
On modélise un problème de satisfaction de contraintes à l'aide de trois ensembles :
- un ensemble de variables,
- un ensemble de valeurs possibles pour chaque variable,
- un ensemble de contraintes qui relient les variables entre elles.
Une solution à un problème de satisfaction de contraintes consiste à trouver une valeur pour chaque variable de façon à ce que toutes les contraintes soient satisfaites. Les
contraintes sont des relations qui doivent être vérifiées sur les variables et les valeurs. Par
exemple, si x et y sont des variables du problème, x x y = 14 est une contrainte. Si x a
pour valeurs possibles 1,2,5 et que y a pour valeurs possibles 5,7, la solution unique au
problème est x = 2 et y = 7.
Dans ce chapitre nous montrons comment programmer des algorithmes simples de
programmation par contraintes. Il existe de nombreux solveurs de contraintes utilisant
des algorithmes bien plus évolués et plus efficaces que ceux que nous montrons, de même
qu'il existe des modélisations plus évoluées que celles que nous utilisons comme par
exemple pour le Sudoku [83].