Le prolog - langage de programmation logique

Résumé du document

Nous allons observer la gestion de contraintes d'affectation au moyen de trois situations différentes. Dans un premier temps, il s'agira de considérer un cas portant sur des élèves en stage. Un hypermarché a accueilli en stage cinq élèves des collèges voisins ; chacun provient d'un collège différent, chacun a été affecté dans un rayon différent et chaque durée de stage est différente. Associer au prénom de chacun, le nom du collège, le rayon où chacun a été affecté, et la durée de stage en sachant que :
- la solution sera présentée sous forme de liste L de 5 éléments [L1,L2,L3,L4,L5] qui sont eux-mêmes des listes de 4 éléments chacune [prénom, collège, rayon, durée], et correspondant à un élève donné (Benoit, Francoise, Lydie, Sébastien ou Stéphanie).
- et on précise les valeurs possibles pour le collège, le rayon ou la durée de la façon suivante grâce au prédicat prend valeur. On utilise le prédicat tout différent pour préciser que les élèves ne viennent pas du même collège, ont été affectés à des rayons différents et ont une durée de stage différente.

Ensuite, il s'agira de placer N reines sur un échiquier de sorte qu'elles ne soient pas en prise, c'est-à-dire qu'aucune d'entre elles ne se trouve sur la même ligne, colonne ou diagonale qu'une autre. Le résultat sera une liste d'affectations consistantes (respectant les contraintes). Les variables X1, X2, … XN sont associées aux N reines :
- Xi désigne la variable associée à la reine de la ligne i
- leur domaine de valeurs Di est la liste L=[1,2, … N]
Le prédicat listent (N,L) constitue une telle liste L en connaissant N.

Enfin, une grille de sudoku se compose de 9 carrés, ayant 3x3 cases. Le but du jeu est de compléter la grille afin que chaque ligne, chaque colonne et chaque carré contiennent tous les chiffres de 1 à 9 une fois et une seule. Le problème du sudoku consiste en fait à faire 9 fois de suite le problème des reines, avec 9 reines à chaque fois, les reines étant, dans ce cas là, des chiffres identiques, et à chaque fois qu'on relance le problème des reines, on change de chiffre à placer (on place d'abord tous les 9, puis tous les 8…).

Extraits

[...] Le résultat sera une liste d'affectations consistantes (respectant les contraintes). 1re partie : L'application listent(N,L) Les variables X1, X XN sont associées aux N reines : Xi désigne la variable associée à la reine de la ligne i Leur domaine de valeurs Di est la liste Le prédicat listent(N,L) constitue une telle liste L en connaissant N. Jeux d'essais : listent(8,L). /*connaissant le nombre de reines*/ L = [ obtient leur domaine de valeurs dans l'ordre décroissant*/ Yes listent(4,[4,3,2,1]). domaine de valeurs est valable dans l'ordre décroissant*/ Yes listent(4,[1,2,3,4]). [...]

[...] On étudie ensuite chacune des conditions spécifiées, et on les traduit en PROLOG : "1. Francoise, qui est au collège Brassens, n'a pas travaillé au rayon ménage; son stage a duré plus d'une semaine." C2==brassens, R2\==menage, "2. Benoit, qui n'est pas du collège Diderot, a effectué le plus long stage; il n'a été affecté ni au rayon vidéo ni au rayon ménage." C1\==diderot, R1\==video, R1\==menage, "3. l'élève du collège Galois, qui n'est ni Benoit ni Stéphanie, a effectué un stage au rayon alimentation d'une durée supérieure à 2 semaines." LGal=[_,galois,alimentation,DGal], appart(LGal,[L2,L3,L4]), appart(DGal,[D2,D3,D4]), DGal>2, "4. [...]

[...] L = [affect(4, affect(3, affect(2, affect(1, ; . retrouve les mêmes solutions sans avoir à entrer les domaines de valeur*/ Code source : appart(X,[X /*appart vaut vrai si X appartient à la liste proposée*/ appart(X,[Y L]):-X\==Y,appart(X,L). backtrack([domaine(X,D)],[affect(X,V)]):-appart(V,D). /*condition d'arrêt*/ backtrack([domaine(X,D) A],[affect(X,V) appart(V,D), appartient au domaine de valeurs*/ backtrack(A,B), /*appel récursif*/ consistant(affect(X,V),B). /*l'affectation est consistante*/ btsol(N,Laff):-inidom(N,Ldom),!,backtrack(Ldom,Laff). /*pour trouver une solution sans avoir à entrer la liste des domaines, le cut sert à ne pas revenir en arrière, c'est-à-dire, ici, à calculer une seule fois la liste de domaines de valeurs*/ 3e partie : Amélioration et critique (forward checking) filtrage(Ldom,Laff) Le prédicat filtrage(Ldom,Laff) construit une liste Laff à partir de la liste Ldom, mais cette fois, à chaque affectation on filtre le domaine de valeurs des variables non encore affectées à l'aide du prédicat filtre(X,V,LdomIn,LdomOut). [...]

[...] retrouve les mêmes solutions*/ Code source : domaine_min([domaine(X,D)],[affect(X,V)]):-appart(V,D). domaine_min(Ldom,[affect(X,Y) plus_petit_domaine(Ldom,domaine(X,D),L),/*choisi le+petit domaine*/ appart(Y,D), vérifie Y appartient au domaine de valeurs*/ filtre(X,Y,L,LdomOut), filtre la liste des domaines de valeurs*/ domaine_min(LdomOut,Laff). /*appel récursif*/ domsol(N,Laff):-inidom(N,Ldom),!,domaine_min(Ldom,Laff). /*pour trouver une solution sans avoir à entrer la liste des domaines*/ plus_petit_domaine(Ldom,domaine(X,D),L) Le prédicat plus_petit_domaine(Ldom,domaine(X,D),L) cherche, parmi tous les éléments de Ldom, celui dont le D est le plus petit, L étant Ldom sans cet élément. Jeux d'essais : plus_petit_domaine([domaine(1,[2,3]),domaine(2,[1,3,4]),domaine(3,[1,4]),dom X = domaine(1, L = [domaine(2, [ domaine(3, domaine(4, [ Yes /*cas d'égalité*/ plus_petit_domaine([domaine(1,[2,3,4]),domaine(2,[1,3,4]),domaine(3,[1,4]),d omaine(4,[1,2,3,4])],X,L). [...]

[...] sur la même diagonale*/ No valide(affect(1,2),affect(2,4)). /*les deux reines sont bien placées*/ Yes valide(affect(1,2),affect(4,X)). ERROR: Arguments are not sufficiently instantiated /*aucun domaine de valeur n'étant défini, le prédicat ne peut pas ‘inventer' de réponse possible*/ Code source : valide(affect(Xi,Vi),affect(Xj,Vj)):-Vi=\=Vj, abs(Xi-Xj)=\=abs(Vi-Vj). 2ème partie : Résolution par recherche dans espaces d'états (backtrack) consistant(Aff,Laff) La liste d'affectations cherchée est une liste progressivement construite : Laff = [affect(Xi,Vi), affect(Xj,Vj), ] où on enregistre : que la valeur Vi a été affectée à Xi, que la valeur Vj a été affectée à Xj Le prédicat consistant(Aff,Laff) teste si une affectation Aff est consistante avec une liste d'affectations Laff déjà effectuées en utilisant le prédicat valide. [...]