Ce que tu décris ressemble à un premier TP de programmation par contraintes. D'autant que j'imagine que les nombres que tu cherches sont des chiffres bien que tu ne l'as pas précisé, donc c'est faisable avec des solveurs de type FD, qui sont très courants. C'est une classe de solveurs qui marchent sur les domaines finis (Finite Domain, d'où leur nom), c'est à dire sur des ensembles de valeurs énumérables, du style "les entiers de 0 à 1000" (par opposition à "les entiers" tout court).
Tu trouveras des solveurs pour différents langage de programmation :
- en programmation logique, tu en as d'intégrés dans pas mal de Prologs, genre dans GNU Prolog [1], Ciao Prolog [2] (libre aussi, et perso je l'aime bien), ou encore Eclipse Prolog [3] (excellent, mais pas complètement libre, ça dépend des morceaux). Je sais plus si y'en a dans SWI Prolog, je le connais à peine.
- en programmation impérative, ça existe sous forme de bibliothèque pour différents langages : C++ mais j'en n'ai plus de nom en tête, Python [4,5], et probablement bien d'autres.
En gros, comme le nom l'indique, c'est un mode de programmation qui consiste (essentiellement) à déclarer des contraintes liants entre elles les valeurs de variables. À la syntaxe prêt, ton énnoncé là haut est un programme (désolé les puristes pour les affreuses simplifications que je vais faire). Il est exécuté par une moulinette qui à l'aide des contraintes réduit les domaines de valeurs possibles des variables, pour converger vers une/des solution(s).
C'est un peu comme quand tu joues au Sudoku : de voir qu'il y a déjà un 9 dans une case te permet d'exclure cette valeur pour les autres de la même ligne ou colonne, et pour le reste du carré, ce qui te permet de déduire la valeur d'une autre case qui n'avait plus beaucoup de possibilité, et elle en influence une autre encore, etc. ; les règles du Sudoku sont en fait un ensemble de contraintes, et l'on raisonne avec de la même façon que fonctionnent ces solveurs, en cherchant à en tirer toutes les conséquences possibles pour arriver à l'unique solution. Évidemment, au Sudoku comme en programmation par contrainte, l'exploitation immédiate et un peu triviale des contraintes directes entre les variables ne suffit pas forcement à aboutir. C'est là qu'intervient l'énumération bourrine des valeurs, qui est possible puisque leur domaine est fini : on prend par exemple une case qui peut valoir soit 2 soit 5, on fait l'hypothèse qu'elle vaut 2, et on voit jusqu'où ça peut nous mener ensuite (à une solution, ou à un échec).
Si tu googles "programmation contraintes", tu trouveras pas mal de cours (c'est au niveau maitrise ou assimilé qu'on enseigne ça souvent), plutôt orientés Prolog en général ("programmation logique avec contraintes" donc), et qui devraient t'aider à t'y mettre sans trop de peine.
Amuses toi bien, tu verras que c'est vraiment un mode de programmation extrêmement plaisant, concis, et efficace, enfin pour les problèmes qui s'y prêtent.
# Programmation par contraintes
Posté par tgl . En réponse au message Générer un tableau à partir de contraintes. Évalué à 5.
Tu trouveras des solveurs pour différents langage de programmation :
- en programmation logique, tu en as d'intégrés dans pas mal de Prologs, genre dans GNU Prolog [1], Ciao Prolog [2] (libre aussi, et perso je l'aime bien), ou encore Eclipse Prolog [3] (excellent, mais pas complètement libre, ça dépend des morceaux). Je sais plus si y'en a dans SWI Prolog, je le connais à peine.
- en programmation impérative, ça existe sous forme de bibliothèque pour différents langages : C++ mais j'en n'ai plus de nom en tête, Python [4,5], et probablement bien d'autres.
En gros, comme le nom l'indique, c'est un mode de programmation qui consiste (essentiellement) à déclarer des contraintes liants entre elles les valeurs de variables. À la syntaxe prêt, ton énnoncé là haut est un programme (désolé les puristes pour les affreuses simplifications que je vais faire). Il est exécuté par une moulinette qui à l'aide des contraintes réduit les domaines de valeurs possibles des variables, pour converger vers une/des solution(s).
C'est un peu comme quand tu joues au Sudoku : de voir qu'il y a déjà un 9 dans une case te permet d'exclure cette valeur pour les autres de la même ligne ou colonne, et pour le reste du carré, ce qui te permet de déduire la valeur d'une autre case qui n'avait plus beaucoup de possibilité, et elle en influence une autre encore, etc. ; les règles du Sudoku sont en fait un ensemble de contraintes, et l'on raisonne avec de la même façon que fonctionnent ces solveurs, en cherchant à en tirer toutes les conséquences possibles pour arriver à l'unique solution. Évidemment, au Sudoku comme en programmation par contrainte, l'exploitation immédiate et un peu triviale des contraintes directes entre les variables ne suffit pas forcement à aboutir. C'est là qu'intervient l'énumération bourrine des valeurs, qui est possible puisque leur domaine est fini : on prend par exemple une case qui peut valoir soit 2 soit 5, on fait l'hypothèse qu'elle vaut 2, et on voit jusqu'où ça peut nous mener ensuite (à une solution, ou à un échec).
Si tu googles "programmation contraintes", tu trouveras pas mal de cours (c'est au niveau maitrise ou assimilé qu'on enseigne ça souvent), plutôt orientés Prolog en général ("programmation logique avec contraintes" donc), et qui devraient t'aider à t'y mettre sans trop de peine.
Amuses toi bien, tu verras que c'est vraiment un mode de programmation extrêmement plaisant, concis, et efficace, enfin pour les problèmes qui s'y prêtent.
[1] http://pauillac.inria.fr/~diaz/gnu-prolog/
[2] http://clip.dia.fi.upm.es/Software/Ciao/
[3] http://www.icparc.ic.ac.uk/eclipse/
[4] http://www.logilab.org/projects/constraint
[5] http://codespeak.net/~niemeyer/constraint/