Programmer en Prolog

Introduction

Prolog est un langage de programmation déclaratif permettant de résoudre des problèmes logiques. Le nom Prolog est l'acronyme de PROgrammation LOGique. Le principe de la programmation logique est de décrire l'énnoncé d'un problème par un ensemble d'expressions et de liens logiques au lieu de définir pas à pas la succession d'instructions que doit exécuter l'ordinateur pour résoudre la problématique.

Sommaire de cette page

Installation de Prolog

Premier programme en Prolog

Exemple 1 : l'arbre généalogique

Exemple 2 : un logigramme simple

Utilisation des listes

Exemple 3 : un logigramme complexe : Qui a le zèbre ?

Exemple 4 : un autre logigramme : les 5 sportifs chez le médecin

Utilisation de la coupure

Exemple 5 : génération des grilles de roulement des TP tournants

Exemple 6 : génération des combinaisons d'une liste sans doublons

Programmation avec contraintes

 

Retour en haut de la page

Installation de Prolog

Plusieurs implémentations de Prolog existent, aussi bien sous Windows que sous Linux.

Parmi elle il y a SWI-Prolog qui est un interpréteur Prolog gratuit et disponible aussi bien sous Windows que sous Linux.

Pour installer SWI-Prolog sous Windows téléchargez la dernière version stable sur le site swi-prolog.org ou cliquez sur le lien suivant pour télécharger la version 6.2.2 datant de 2012 :

Télécharger SWI-Prolog 6.2.2 (version 2012) pour Windows

 

Pour installer SWI-Prolog sous Linux Ubuntu 10.04 LTS il faut installer le paquet swi-prolog :

apt-get install swi-prolog (ou utiliser l'interface graphique Synaptic d'apt-get).

Pour appeler l'interpréteur SWI-Prolog en ligne de commande sous Linux il faut lancer la commande swipl.

 

On peut également citer YAP et GNU Prolog sous Linux qui sont deux autres implémentations libres de Prolog.

Pour installer YAP sous Linux Ubuntu 10.04 LTS il faut installer le paquet yap :

apt-get install yap (ou utiliser l'interface graphique Synaptic d'apt-get).

Pour appeler l'interpréteur YAP en ligne de commande sous Linux il faut lancer la commande yap.

 

Pour installer GNU Prolog sous Linux Ubuntu 10.04 LTS il faut installer le paquet gprolog :

apt-get install gprolog (ou utiliser l'interface graphique Synaptic d'apt-get).

Pour appeler l'interpréteur gProlog en ligne de commande sous Linux il faut lancer la commande gprolog.

 

Retour en haut de la page

 

Premier programme pour tester l'interpréteur Prolog

Contrairement aux langages de programmation impératifs (comme le Pascal, le langage C, le Java, le Perl, etc.) on ne trouvera pas de boucles For, de test If, de "fonctions", etc. dans Prolog.

Bien que la tradition veuille que le premier programme de test affiche "Bonjour" à l'écran, pour une fois nous allons faire autre chose.

Editons un nouveau fichier texte nommé toto.pl (dans Gedit sous Linux ou dans le bloc note sous Windows) :

gedit toto.pl

Voici le code source en Prolog de ce premier programme qui se contente de déclarer un ensemble de faits :

animal(chien).
animal(chat).
prenom(paul).
prenom(pierre).
prenom(jean).

Voici les faits affirmés par notre programme :

Ouvrons le programme source toto.pl dans l'interpréteur Prolog :

consult(toto).

Remarques :

Nous n'allons pas maintenant "exécuter" le programme, mais nous allons poser à l'interpréteur Prolog un ensemble de questions pour lesquelles l'interpréteur consultera les faits et les règles inscrits dans le programme.

Première question : jean est-il un prénom ?

?- prenom(jean).

L'interpréteur nous répond true : jean est bien un prénom dans la base des faits inscrits dans le programme.

Deuxième question : vincent est-il un prénom ?

?- prenom(vincent).

L'interpréteur nous répond false : vincent n'est pas un prénom dans la base des faits inscrits dans le programme.

Autre question : quels sont tous les animaux ?

?- animal(X).

La variable X va prendre pour valeur chaque nom d'animal. Pour passer d'un valeur à une autre il faut appuyer sur la touche point-virgule. Une fois que la liste est terminée, Prolog la fini par un point. Le résultat est alors :

X = chien;
X = chat.

Autre question : quels sont tous les prenoms ?

?- prenom(X).

Cette fois la variable X va prendre pour valeur chaque prénom. Le point-virgule permet toujours de passer d'une réponse à la suivante. Le résultat final est alors :

X = paul;
X = pierre;
X = jean.

Autre question : existe-t-il des animaux ?

?- animal(_).

Cette fois l'expression animal(_) sera vraie chaque fois que Prolog rencontre un animal (peut importe lequel) dans la base des faits du programme. Comme Prolog rencontre 2 animaux, la réponse à notre question est :

true ;
true.

La commande listing permet d'afficher le code source de la base de faits du programme courant :

?- listing.

Enfin, la commande halt permet de sortir de l'interpréteur Prolog :

?- halt.

 

Retour en haut de la page

 

Exemple 1 : l'arbre généalogique

Les données du problème sont : Alice et Luc sont mariés. Luc est le père de Jean.

La problématique à résoudre est : Qui est la mère de Jean ?

Dans le code source nous indiquons que :

Puis nous indiquons à Prolog que si un père est mariè à une femme, alors cette dernière est la mère du fils :

% les faits :
epouse(alice,luc). % alice est l'épouse de luc
pere(luc,jean). % luc est le père de jean

% les règles :
mere(M,E):-pere(P,E),epouse(M,P). % M est la mère de E si P est le père de E et si M est l'épouse de P

Remarque : en Prolog tout ce qui suit le caractère % sur une ligne est un commentaire.

Aprés avoir ouvert le programme dans l'interpréteur Prolog (par la commande consult), posons lui quelques questions :

Question 1 : qui est l'épouse de luc ?

?- epouse(X,luc).

Réponse :

X = alice.

Question 2 : qui est l'époux d'alice ? (qui a pour épouse alice)

?- epouse(alice,X).

Réponse :

X = luc.

Question 3 : qui est le père de jean ?

?- pere(X,jean).

Réponse :

X = luc.

Question 4 : qui est le fils de luc ? (qui a pour père luc)

?- pere(luc,X).

Réponse :

X = jean.

Remarque : pour répondre à ces 4 premières questions Prolog n'a utiliser que les faits, sans utiliser la règle définissant la mère.

Question 5 : qui est la mere de jean ?

?- mere(X,jean).

Réponse :

X = alice.

Question 6 : qui est le fils d'alice ? (qui a pour mère alice)

?- mere(alice,X).

Réponse :

X = jean.

Remarque : pour répondre à ces 2 dernières questions Prolog a utiliser cette fois la règle définissant la mère.

Question 7 : qui est le fils de jean ? (qui a pour père jean)

?- pere(jean,X).

Réponse :

false.

Question 8 : qui est le fils de lucienne ? (qui a pour mère lucienne)

?- mere(lucienne,X).

Réponse :

false.

Remarque : Prolog n'a pas la réponse à ces 2 dernières questions : il répond alors false.

Question 9 : qui est la mère de qui ?

?- mere(X,Y).

Réponse :

X = alice,
Y = jean.

Question 10 : combien de liens de parenté "mère/fils" existe-t-il ?

?- mere(_,_).

Réponse : 1 seul

true.

Question 11 : existe-t-il une personne qui est sa propre mère ?

?- mere(X,X).

Réponse : NON

false.

Remarque : en Prolog le nom des variables commencent toujours par une lettre majuscule (exemple : X, Voiture, NUMERO, etc.).

Retour en haut de la page

 

Exemple 2 : un logigramme simple

Les données du problème sont :

La problématique à résoudre est :

Le programme source en Prolog :

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Réalisé par Jean-Christophe MICHEL
% Juillet 2011
% www.gecif.net
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%--------------------------------------------------------
% les faits :

% les 3 maisons :
maison(chateau).
maison(studio).
maison(pavillon).

% les 3 animaux :
animal(chat).
animal(poisson).
animal(cheval).

%--------------------------------------------------------
% les règles :

% le prédicat relation constitue la relation entre une personne, son animal et sa maison :
relation(max,M,chat):-maison(M).
relation(luc,studio,A):-animal(A),A\==cheval.
relation(eric,M,A):-maison(M),M\==pavillon,animal(A).

% le prédicat different est vraie seulement si ses 3 paramètres sont différents :
different(X,X,_):-!,fail.
different(X,_,X):-!,fail.
different(_,X,X):-!,fail.
different(_,_,_).

% le prédicat "resoudre" indique les 4 inconnues à retrouver :
resoudre(MM,ME,AE,AL):-

relation(max,MM,chat),
relation(eric,ME,AE),
different(MM,ME,studio),
relation(luc,studio,AL),
different(AE,AL,chat).

Demandons à l'interpréteur Prolog de résoudre le problème en proposant une valeur pour chacune des 4 inconnues :

resoudre(MM,ME,AE,AL).

Et la réponse immédiate est :

MM = pavillon,
ME = chateau,
AE = cheval,
AL = poisson .

Ce qui signifie en clair que :

La problématique à résoudre était :

 

Retour en haut de la page

 

Utilisation des listes

Les tableaux tels qu'on les connaît dans les langages impératifs n'existent pas en Prolog. Ils sont remplacés par les listes.

Une liste en Prolog s'écrit entre crochets. Exemple : [a,b,c] est une liste contenant les 3 éléments a, b et c. A l'intérieur d'une liste les éléments sont séparés par une virgule losqu'ils sont énumérés un à un.

La liste vide est représentée par [].

L'opérateur | (barre verticale) permet de définir une liste constituée de :

[X|L] est une liste obtenue en ajoutant l'élément X au début de la liste L.

Par exemple les écritures suivantes sont toutes équivalentes : [a|[b,c]] = [a|[b|[c]]] = [a|[b|[c|[]]]] = [a,b,c]

Affichage de tous les éléments d'une liste

Le programme source est :

afficher_liste([X|L]) :- writeln(X), afficher_liste(L).

Aprés avoir ouvert ce programme simple dans l'interpréteur Prolog (par la commande consult), utilisons la fonction afficher_liste :

Question :

?- afficher_liste([a,b,c]).

Réponse :

a
b
c
false.

Question :

?- afficher_liste([a|[b|[c|[]]]]).

Réponse :

a
b
c
false.

Test de l'appartenance à une liste

Le programme source est :

appartient_a(X,[X|_]).
appartient_a(X,[_|L]) :- appartient_a(X,L).

Aprés avoir ouvert ce programme simple dans l'interpréteur Prolog (par la commande consult), utilisons la fonction appartient_a :

Question :

?- appartient_a(a,[a,b,c]).

Réponse :

true

Question :

?- appartient_a(c,[a,b,c]).

Réponse :

true

Question :

?- appartient_a(e,[a,b,c]).

Réponse :

false

Les prédicats prédéfinis de SWI-Prolog pour la manipulation des listes

Voici quelques prédicats prédéfinis dans SWI-Prolog et bien pratiques pour la manipulation des listes sans devoir les ré-écrire. Le nombre de paramètres attendus par un prédicat est appelé son arité et il est précisé en suffixe après le / dans les noms des prédicats. Exemple : member/2 signifie le prédicat member utilisant 2 paramètres.

Prédicat
Syntaxe
Rôle
Exemple
member/2
member(X,L)
vrai si l'élément X appartient à la liste L
member(b,[a,b,c])
subset/2
subset(L1,L2)
vrai si tous les éléments de L1 sont présents dans L2
subset([a,c],[a,b,c])
sublist/3
sublist(P,L1,L2)
crée L2 avec les éléments de L1 pour qui le prédicat P est vrai
sublist(<(3),[1,2,3,4,5,6],L)
append/3
append(L1,L2,L3)
vrai si la liste L3 est la concaténation des listes L1 et L2
append([a,b],[c,d,e],L)
permutation/2
permutation(L1,L2)
vrai si L1 est une permutation de L2
permutation([a,b,c],L)
flatten/2
flatten(L1,L2)
applanit et unifie une liste composée L1 pour créer L2
flatten([[a,b],[c,d],e],L)
nth1/3
nth1(N,L,X)
vrai si la liste L possède l'élément X à la position N
nth1(2,[7,9,12,45],9)
length/2
length(L,N)
vrai si L est une liste composée de N éléments
length([1,2,3,4,5],X)
numlist/3
numlist(MIN,MAX,L)
crée une liste numérique L composée des entiers allant de MIN à MAX
numlist(2,9,L)
maplist/2
maplist(P,L)
applique le prédicat P sur chaque élément de la liste L
maplist(writeln,[1,2,3,4,5])
sort/2
sort(L1,L2)
trie les éléments de L1 pour créer L2
sort([b,d,c,a],L)
list_to_set/2
list_to_set(L1,L2)
supprime les doublons dans L1 pour créer L2
list_to_set([a,b,c,a,d,c,b],L)
select/3
select(X,L1,L2)
X prend pour valeur chaque élément de la liste L1, et la liste L2 est égale à L1 privée de l'élément X
select(X, [1,2,3,4], L)
findall/3
findall(X,P,L)
crée la liste L contenant toutes les solutions X fournies par un prédicat P
findall(Y,select(X,[1,2,3,4,5],Y),L)

Exemple d'application : on désire obtenir une liste L composée de 50 sous-listes, chacune des 50 sous-listes devant contenir tous les entiers de 1 à 50 sauf un. La ligne suivante génère la liste L :

?- numlist(1,50,M),findall(Y,select(X,M,Y),L).

Demandons d'applanir la liste L pour créer une liste A :

?- numlist(1,50,M),findall(Y,select(X,M,Y),L),flatten(L,A).

Demandons de supprimer les doublons dans la liste A pour créer une liste B :

?- numlist(1,50,M),findall(Y,select(X,M,Y),L),flatten(L,A),list_to_set(A,B).

Enfin demandons à Prolog d'ordonner les éléments de la liste B pour créer la liste C :

?- numlist(1,50,M),findall(Y,select(X,M,Y),L),flatten(L,A),list_to_set(A,B),sort(B,C).

On obtient alors naturellement au final pour la liste C une liste ordonnée des entiers de 1 à 50.

Cet exemple a montré comment enchaîner les différents prédicats afin d'affiner la génération d'une liste formatée.

 

Exemple d'application des listes : résolution d'un nouveau logigramme simple "Qui a le serpent ?"

Dans une rue 3 maisons voisines sont de couleurs différentes : rouge, bleue et verte. Des personnes de nationalités différentes vivent dans ces maisons et elles ont chacune un animal de compagnie différent.

Les données du problème sont :

La problématique à résoudre est :

Le programme source en Prolog ne contient qu'un seul prédicat serpent/1 :

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Solution en Prolog du problème "Qui a le serpent ?" %
% Réalisé par Jean-Christophe MICHEL                  %
% Juin 2015                                           %
% www.gecif.net                                       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

serpent(N) :-
    % Rue est une liste de 3 maisons :
    Rue=[Maison1,Maison2,Maison3],
    % une maison est rouge :
    member(maison(rouge,_,_),Rue),
    % une maison est bleue :
    member(maison(bleu,_,_),Rue),
    % une maison est verte :
    member(maison(vert,_,_),Rue),
    
% l'anglais est dans la maison rouge :
    member(maison(rouge,anglais,_),Rue),
    % l'espagnol possède le jaguar :
    member(maison(_,espagnol,jaguar),Rue),
    % le japonais ne possède pas l'escargot :
    subset([maison(_,_,escargot),maison(_,japonais,_)],Rue),
    % l'escargot n'est pas dans la maison bleue :
    subset([maison(bleu,_,_),maison(_,_,escargot)],Rue),
    % le troisième animal est un serpent :
    member(maison(_,N,serpent),Rue).

Appelons le pédicat serpent/1 dans SWI-Prolog : il nous donne instantanément la nationalité du possesseur du serpent

?- serpent(X).
X = japonais

On en déduit alors une composition possible pour les maisons en utilisant les données de l'énoncé :

Maison 1
Maison 2
Maison 3
rouge
anglais
escargot
bleue
espagnol
jaguar
verte
japonais
serpent

Remarque : le fait "le japonais vit à droite de la maison du possesseur de l'escargot" dans l'énoncé indique seulement que le japonais ne possède pas l'escargot (écrit subset([maison(_,_,escargot),maison(_,japonais,_)],Rue) dans le programme). De même la condition "le possesseur de l'escargot vit à gauche de la maison bleue" indique que l'escargot n'est pas dans la maison bleue (noté subset([maison(bleu,_,_),maison(_,_,escargot)],Rue) dans le programme).

La position relative des maisons 2 et 3 n'a alors aucune importance, et la solution suivante pour la composition des maisons est également correcte :

Maison 1
Maison 2
Maison 3
rouge
anglais
escargot
verte
japonais
serpent
bleue
espagnol
jaguar

Et si on demandait à Prolog de nous sortir toutes les compositions des maisons correspondantes à l'énoncé ? Ajoutons au prédicat serpent un second paramètre correspondant à la liste Rue :

serpent(N,Rue) :-
   Rue=[Maison1,Maison2,Maison3],
   member(maison(rouge,_,_),Rue),
   member(maison(bleu,_,_),Rue),
   member(maison(vert,_,_),Rue),
   member(maison(rouge,anglais,_),Rue),
   member(maison(_,espagnol,jaguar),Rue),
   subset([maison(_,_,escargot),maison(_,japonais,_)],Rue),
   subset([maison(_,_,escargot),maison(bleu,_,_)],Rue),
   member(maison(_,N,serpent),Rue).

Appelons le nouveau prédicat serpent/2, et là ... surprise :

?- serpent(X,Y).
X = japonais,
Y = [maison(rouge, anglais, escargot), maison(bleu, espagnol, jaguar), maison(vert, japonais, serpent)] ;

X = japonais,
Y = [maison(rouge, anglais, escargot), maison(bleu, japonais, serpent), maison(vert, espagnol, jaguar)] ;
X = japonais,
Y = [maison(rouge, anglais, escargot), maison(vert, espagnol, jaguar), maison(bleu, japonais, serpent)] ;
X = japonais,
Y = [maison(rouge, anglais, escargot), maison(vert, japonais, serpent), maison(bleu, espagnol, jaguar)] ;
X = japonais,
Y = [maison(bleu, espagnol, jaguar), maison(rouge, anglais, escargot), maison(vert, japonais, serpent)] ;
X = anglais,
Y = [maison(bleu, japonais, escargot), maison(rouge, anglais, serpent), maison(vert, espagnol, jaguar)] ;
X = japonais,
Y = [maison(vert, espagnol, jaguar), maison(rouge, anglais, escargot), maison(bleu, japonais, serpent)] ;
X = anglais,
Y = [maison(vert, japonais, escargot), maison(rouge, anglais, serpent), maison(bleu, espagnol, jaguar)] ;
X = anglais,
Y = [maison(bleu, espagnol, jaguar), maison(vert, japonais, escargot), maison(rouge, anglais, serpent)] ;
X = anglais,
Y = [maison(bleu, japonais, escargot), maison(vert, espagnol, jaguar), maison(rouge, anglais, serpent)] ;
X = anglais,
Y = [maison(vert, espagnol, jaguar), maison(bleu, japonais, escargot), maison(rouge, anglais, serpent)] ;
X = anglais,
Y = [maison(vert, japonais, escargot), maison(bleu, espagnol, jaguar), maison(rouge, anglais, serpent)] ;
false.

Prolog nous sort 12 compositions possibles des maisons mais sans notion d'ordre : il ne faut garder que les solutions correspondant aux conditions suivantes (l'escargot est à gauche du japonais et à gauche de la maison bleue) :

Il s'agit des 5 solutions en rouge ci-dessus.

Dans tous les cas on en déduit que c'est forcément le japonais qui possède le serpent, seule question posée par le problème qui ne demandait pas la composition complète des maisons.

Mais pour Prolog l'anglais aussi peut très bien posséder le serpent : l'énoncé n'est pas assez précis, la solution n'est pas unique, et la notion d'ordre n'a pas été indiquée à Prolog.

Cet exemple a montré comment résoudre un logigramme simple en Prolog en utilisant seulement les prédicats prédéfinis member/2 et subset/2 de SWI-Prolog, et sans écrire de nouveaux prédicats pour la manipulation des listes.

 

Retour en haut de la page

 

Exemple 3 : un logigramme complexe : Qui a le zèbre ?

L'énnoncé du problème est le suivant :

Cinq hommes de nationalités et de professions différentes habitent des maisons de couleurs différentes et situés côte à côte dans le même alignement. Ils ont chacun un animal favori et une boisson préférée.

Les données du problème sont :

La problématique à résoudre est :

La difficulté est la suivante :

Le programme source en Prolog :

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Solution en Prolog du problème "Qui a le zèbre ?" %
% Réalisé par Jean-Christophe MICHEL                %
% Juillet 2011                                      %
% www.gecif.net                                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%--------------------------------------------------------
% les faits :

% liste_des_maisons est une liste de 5 maisons.
% Chaque maison a 5 paramètres qui seront dans l'ordre :
% - couleur

% - nationalité
% - animal
% - boisson
% - profession
% exemple : maison(jaune,norvegien,renard,eau,diplomate)


liste_des_maisons([
maison(_, _, _, _, _),
maison(_, _, _, _, _),
maison(_, _, _, _, _),
maison(_, _, _, _, _),
maison(_, _, _, _, _)
]).

%--------------------------------------------------------
% les règles :

% afficher_liste(L) : affiche un à un les éléments de la liste L avec retour à la ligne (writeln)
afficher_liste([X|L]) :- writeln(X), afficher_liste(L).

% appartient_a(X,L) : vrai si l'élément X appartient à la liste L
appartient_a(X,[X|_]).
appartient_a(X,[_|L]) :- appartient_a(X,L).

% est_a_droite_de(A,B,L) : vrai si A suit B dans la liste L
est_a_droite_de(A, B, [B, A | _]).
est_a_droite_de(A, B, [_ | Y]) :- est_a_droite_de(A, B, Y).

% est_voisin_de(A,B,L) : vrai si A et B sont consécutifs dans la liste L
est_voisin_de(A, B, [A, B | _]).
est_voisin_de(A, B, [B, A | _]).
est_voisin_de(A, B, [_ | Y]) :- est_voisin_de(A, B, Y).

% pour que le prédicat "resoudre" aboutisse il faut que toutes les conditions soient remplies :
resoudre :-

% la seule variable du programme est MAISONS : il s'agit d'une liste de 5 éléments "maison" :
liste_des_maisons(MAISONS),

% l'anglais habite la maison rouge :
appartient_a(maison(rouge, anglais, _, _, _), MAISONS),

% l'espagnol a un chien :
appartient_a(maison(_,espagnol, chien,_,_), MAISONS),

% dans la maison verte on boit du café :
appartient_a(maison(verte,_,_,cafe,_), MAISONS),

% l'ukrainien boit du thé :
appartient_a(maison(_,ukrainien,_,the,_), MAISONS),

% la maison verte est immédiatement à droite de la maison blanche :
est_a_droite_de(maison(verte,_,_,_,_), maison(blanche,_,_,_,_), MAISONS),

% le sculpteur élève des escargots :
appartient_a(maison(_,_,escargots,_,sculpteur), MAISONS),

% le diplomate habite la maison jaune :
appartient_a(maison(jaune, _, _, _, diplomate), MAISONS),

% dans la maison du milieu on boit du lait :
MAISONS = [_, _, maison(_, _, _, lait, _), _,_],

% le norvégien habite la première maison à gauche :
MAISONS = [maison(_, norvegien, _, _, _)|_],

% le médecin habite une maison voisine de celle où demeure le propriétaire du renard :
est_voisin_de(maison(_,_,_,_,medecin), maison(_,_,renard,_,_), MAISONS),

% la maison du diplomate est à côté de celle où il y a un cheval :
est_voisin_de(maison(_,_,_,_,diplomate), maison(_,_,cheval,_,_), MAISONS),

% le violoniste boit du jus d'orange :
appartient_a(maison(_,_,_,jus,violoniste), MAISONS),

% le japonais est acrobate :
appartient_a(maison(_,japonais,_,_,acrobate), MAISONS),

% le norvégien habite à côté de la maison bleue :
est_voisin_de(maison(_,norvegien,_,_,_), maison(bleue,_,_,_,_), MAISONS),

% on précise que dans une des maisons on boit de l'eau :
appartient_a(maison(_,_,_,eau,_), MAISONS),

% on précise que dans une des maisons il y a un zèbre :
appartient_a(maison(_,_,zebre,_,_), MAISONS),

% affiche la liste finale seulement si toutes les conditions précédentes sont remplies :
afficher_liste(MAISONS).

Demandons à l'interpréteur Prolog de résoudre le problème en affichant la composition de chaque maison :

resoudre.

Et la réponse immédiate est :

maison(jaune,norvegien,renard,eau,diplomate)
maison(bleue,ukrainien,cheval,the,medecin)
maison(rouge,anglais,escargots,lait,sculpteur)
maison(blanche,espagnol,chien,jus,violoniste)
maison(verte,japonais,zebre,cafe,acrobate)
false.

Ce qui signifie en clair que la composition des maisons est :

Maison 1
Maison 2
Maison 3
Maison 4
Maison 5
jaune
norvégien
renard
eau
diplomate
bleue
ukrainien
cheval
thé
médecin
rouge
anglais
escargots
lait
sculpteur
blanche
espagnol
chien
jus d'orange
violoniste
verte
japonais
zèbre
café
acrobate

La problématique à résoudre était :

  • Qui boit de l'eau ? Réponse : Le norvégien
  • Qui possède le zèbre ? Réponse : Le japonais

 

Remarque : avec l'énnoncé complet la solution est unique. Si on supprime une des conditions dans l'énoncé, il y a alors plusieurs solutions. Pour le tester facilement il suffit de commenter une des conditions dans le prédicat resoudre en mettant un signe % en début de ligne puis de redemander à Prolog d'afficher la solution : il affichera alors toutes les solutions possibles.

En supprimant plusieurs conditions le nombre de solutions possibles devient vite très important. Pour avoir le temps de regarder chaque solution on pourra modifier la fonction afficher_liste en lui demandant d'afficher un séparateur à la fin de chaque liste :

% appel récursif si la liste à afficher contient plusieurs éléments :
afficher_liste([X|L]) :- writeln(X), afficher_liste(L).
% affiche un séparateur si la liste ne contient plus qu'un seul élément :
afficher_liste([X]) :- writeln(X), writeln(-----------------------------------------------).

Avec cette nouvelle fonction afficher_liste il faudra appuyer sur la touche point-virgule pour passer à la solution suivante.

 

Retour en haut de la page

 

Exemple 4 : un autre logigramme : les 5 sportifs chez le médecin

L'énnoncé du problème est le suivant :

Cinq sportifs sont dans la salle d'attente d'un médecin spécialisé.

Retrouvez grâce aux indications suivantes leur ordre d'arrivée, le sport pratiqué par chacun ainsi que la raison de leur présence.

La première difficulté par rapport au logigramme du zèbre sont les conditions de négation, du style "Christian ne pratique pas la gymnastique". Pour inclure ces conditions dans le prédicat resoudre nous allons nous inspirer du logigramme simple donné à l'exemple 2 ci-dessus en utilisant l'opérateur \== permettant d'indiquer qu'une variable n'est pas égale à telle valeur.

Pour résoudre la notion d'ordre dans des conditions du style "Grégoire est arrivé avant Laurent" nous allons utiliser les listes comme dans le logigramme du zèbre donné à l'exemple 3 ci-dessus. Mais contrairement au logigramme du zèbre on ne veut pas détecter ici deux éléments "voisins" (c'est-à-dire qui se suivent dans la liste). La condition "Grégoire est arrivé avant Laurent" ne signifie pas que Gégoire est arrivé juste avant Laurent. C'est la raison pour laquelle nous ne pouvons pas ré-utiliser directement les fonctions est_voisin_de ou est_a_droite_de données dans le logigramme du zèbre.

La seconde difficulté est donc de détecter l'ordre des éléments dans une liste. Pour détecter qu'un élément est avant un autre dans une liste nous allons utiliser la fonction append de Prolog :

append attend en paramètre 3 listes : append(L1,L2,L3)

append sera vrai si la liste L3 est la concaténation des listes L1 et L2

Exemple 1 : la liste [a,b] est-elle la concaténation des listes [a] et [b] :

?- append([a],[b],[a,b]).
true.

Exemple 2 : la concaténation des listes [a,b] et [c,d] donne-t-elle la liste [a,b,c,d,e] ?

?- append([a,b],[c,d],[a,b,c,d,e]).
false.

Exemple 3 : la liste [a,b,c] possède-t-elle une sous-liste commençant par [b] ?

?- append(_,[b|_],[a,b,c]).
true.

Exemple 4 : la liste [a,b,c] commence-t-elle par [b] : le premier élément de la liste est-il b ?

append([b],_,[a,b,c]).
false.

Exemple 5 : le dernier élément de la liste [a,b,c] est-il c ?

?- append(_,[c],[a,b,c]).
true.

Grâce à append, la fonction suivante permet de savoir si l'élément A est avant l'élément B dans la liste L, sans forcément que les éléments A et B soient consécutifs dans la liste :

% est_avant(A,B,L) : vrai si l'élément A est avant l'élément B dans la liste L
est_avant(A, B, L) :-
    append(_, [A | X], L), % il existe une sous-liste de L qui commence par A
    append(_, [B | _], X). % et il existe une sous-liste de X qui commence par B

Enfin, toujours grâce à append, il est possible de simplifier la fonction appartient_a :

% appartient_a(X,L) : vrai si l'élément X appartient à la liste L
appartient_a(X,L) :- append(_,[X|_],L).

La solution de cet exemple 4 est donc "un mélange" des exemples 2 et 3 ci-dessus avec en plus l'utilisation de la fonction append.

Voici le programme source en Prolog de cet exemple 4 :

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Solution en Prolog du problème des 5 sportifs     %
% Réalisé par Jean-Christophe MICHEL                %
% Novembre 2012                                     %
% www.gecif.net                                     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

liste_des_sportifs([
sportif(_, _, _),
sportif(_, _, _),
sportif(_, _, _),
sportif(_, _, _),
sportif(_, _, _)
]).

% afficher_liste(L) : affiche un à un les éléments de la liste L avec retour à la ligne (writeln)
afficher_liste([X|L]) :- writeln(X), afficher_liste(L).

% appartient_a(X,L) : vrai si l'élément X appartient à la liste L
appartient_a(X,L) :- append(_,[X|_],L).

% est_arrive_avant(A,B,L) : vrai si l'élément A est avant l'élément B dans la liste L
est_arrive_avant(A, B, L) :-
    append(_, [A | X], L), % il existe une sous-liste de L qui commence par A
    append(_, [B | _], X). % et il existe une sous-liste de X qui commence par B

% pour que le prédicat "resoudre" aboutisse il faut que toutes les conditions soient remplies :
resoudre :-

% la variable SPORTIFS est une liste ordonnée de 5 éléments "sportif" :
liste_des_sportifs(SPORTIFS),

% on précise les 2 sports qui ne sont pas utilisés dans les conditions ci-dessous :
appartient_a(sportif(_, basket, _), SPORTIFS),
appartient_a(sportif(_, rugby, _), SPORTIFS),

% on précise les 3 motifs de consultation qui ne sont pas utilisés dans les conditions ci-dessous :
appartient_a(sportif(_, _, certificat), SPORTIFS),
appartient_a(sportif(_, _, renouvellement), SPORTIFS),
appartient_a(sportif(_, _, visite), SPORTIFS),

% on précise le prénom qui n'est pas utilisé dans les conditions ci-dessous :
appartient_a(sportif(remi, _, _), SPORTIFS),

% jean est arrivé en dernier :
SPORTIFS = [_,_,_,_,sportif(jean, _, _)],

% la variable SJ représente le Sport de Jean :
appartient_a(sportif(jean, SJ, _), SPORTIFS),
SJ\==gymnastique, % jean ne fait pas de gymnastique
SJ\==basket, % jean ne fait pas de basket

% la variable MJ représente le Motif de consultation de Jean :
appartient_a(sportif(jean, _, MJ), SPORTIFS),
MJ\==certificat, % jean ne veut pas de certificat

% la variable SC représente le Sport de Christian :
appartient_a(sportif(christian, SC, soin), SPORTIFS),
SC\==gymnastique, % christian, venu pour un soin, ne pratique pas la gymnastique

% gregoire qui est arrivé avant laurent fait du patinage :
est_arrive_avant(sportif(gregoire, patinage, _), sportif(laurent, _, _), SPORTIFS),

% gregoire (qui fait du patinage) est arrivé après celui qui fait de la gymnastique :
est_arrive_avant(sportif(_, gymnastique, _), sportif(gregoire, patinage, _), SPORTIFS),

% la variable MG représente le Motif de consultation de Grégoire :
appartient_a(sportif(gregoire, _, MG), SPORTIFS),
MG\==certificat, % gregoire ne veut pas de certificat
MG\==renouvellement, % gregoire ne veut pas de renouvellement

% celui qui pratique le football est arrivé le troisième. Il est venu chercher une dispense :
SPORTIFS = [_, _, sportif(_, football, dispense), _, _],

% celui qui pratique le football est arrivé avant Christian :
est_arrive_avant(sportif(_, football, _), sportif(christian, _, _), SPORTIFS),

% affiche la liste finale seulement si toutes les conditions précédentes sont remplies :
afficher_liste(SPORTIFS).

Demandons à l'interpréteur Prolog de résoudre le problème en affichant l'ordre d'arrivée, le prénom, le sport, et le motif de consultation de chaque sportif :

resoudre.

Et la réponse immédiate est une liste ordonnée et unique (il y a une seule solution au problème) des 5 sportifs :

sportif(remi,gymnastique,certificat)
sportif(gregoire,patinage,visite)
sportif(laurent,football,dispense)
sportif(christian,basket,soin)
sportif(jean,rugby,renouvellement)
false.

On en déduit que le premier arrivé est Rémi, puis Grégoire, puis Laurent, puis Christian, et enfin le dernier arrivé est Jean, et pour chaque sportif Prolog nous indique dans la liste le sport pratiqué et le motif de consultation.

Ce qui signifie en clair que la solution du problème est :

Ordre d'arrivée
Prénom
Sport
Motif
1
2
3
4
5
Rémi
Grégoire
Laurent
Christian
Jean
gymnastique
patinage
football
basket
rugby
certificat
visite
dispense
soin
renouvellement

 

 

 

Retour en haut de la page

 

Utilisation de la coupure

La coupure est un prédicat prédéfini très important qui a pour effet de stopper la recherche de Prolog dès qu'il aura trouvé une solution.

Ce prédicat permet de contrôler l'espace de recherche et d'économiser le travail de Prolog en limitant l'exploration de l'arbre de recherche.

La coupure se note ! (un point d'exclamation) dans la plupart des versions de Prolog.

Rappelons que le prédicat prédéfini is est l'opérateur d'affectation en Prolog : il affecte à la variable de gauche la valeur de l'expression de droite, après avoir évalué cette expression. Par exemple, X is A+2. évalue en un premier temps l'expression A+2 puis affecte le résultat à la variable X.

Exemple simple :

?- X is 2, Y is X+3.
X = 2,
Y = 5.

Passons à 3 exemples d'utilisation concrètes de la coupure en Prolog.

Exemple 1 de la coupure : affichage de tous les entiers de N à 1 dans l'ordre décroissant

L'idée de base est d'écrire un prédicat afficher(N) qui s'appelle récurcivement en passant en paramètre au prédicat appelé la valeur N-1 :

afficher(N):-writeln(N),K is N-1,afficher(K).

Le problème est que cet appel récurcif ne s'arrête jamais, et affiche toutes les valeurs négatives sans fin :

?- afficher(5).
5
4
3
2
1
0
-1
-2
-3
-4
-5
-6
-7
-8
-9
-10
-11
-12
-13
-14
-15
-16
-17
-18
-19

etc. sans arrêt ...

Une solution pour arrêter l'affichage en dessous de zéro est de rajouter une condition dans le prédicat afficher(N) :

afficher(N):-N>0,writeln(N),K is N-1,afficher(K).

Cela stope en effet l'affichage à 1, mais Prolog répond alors par la négation (false) en sortant lorque N=0 car la condition N>0 n'est pas vérifiée :

?- afficher(5).
5
4
3
2
1
false.

La solution pour stopper l'affichage lorsque N=0 tout en répondant positivement (true) est d'utiliser la coupure : on stoppe positivement la recherche lorsque N=0, c'est-à-dire lorsque le prédicat afficher() reçoit 0 en paramètre :

afficher(0):-!. % ne fait rien et arrête la recherche en répondant true
afficher(N):-writeln(N),K is N-1,afficher(K). % appel récurcif du prédicat afficher()

Et le résultat est :

?- afficher(5).
5
4
3
2
1
true.

 

Exemple 2 de la coupure : affichage de tous les éléments d'une liste

L'idée de base est d'écrire un prédicat afficher([X|Y]) qui affiche le premier élément X puis qui appelle récurcivement le prédicat afficher en lui passant en paramètre le reste Y de la liste:

afficher([X|Y]):-writeln(X),afficher(Y).

Mais là encore Prolog répond par la négation (false) lorsqu'il n'y a plus rien à afficher, c'est-à-dire lorsque la liste reçue en paramètre par le prédicat afficher est vide :

?- afficher([a,b,c,d]).
a
b
c
d
false.

La solution consiste donc à préciser grâce à la coupure que si la liste reçue est vide, on arrête la recherche et on répond positivement :

afficher([]):-!. % arrête si la liste est vide
afficher([X|Y]):-writeln(X),afficher(Y). % appel récurcif si la liste n'est pas vide

Et le résultat est :

?- afficher([a,b,c,d]).
a
b
c
d
true.

 

Exemple 3 de la coupure : répétition d'une proposition quelconque

Le prédicat repeter(N,P) suivant répètre N fois la proposition P :

repeter(0,_):-!. % arrête si N=0 quelque soit la proposition P
repeter(N,P):-P,X is N-1,repeter(X,P). % exécute P puis appel récurcif

Exemples d'utilisation :

?- repeter(5,write('bonjour ')).
bonjour bonjour bonjour bonjour bonjour
true.

?- repeter(5,repeter(3,writeln('gecif'))).
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
gecif
true.

?- repeter(4,(write('prolog'),nl)).
prolog
prolog
prolog
prolog
true.

Remarques :

?- repeter(4,(write('prolog'),writeln(''))).
prolog
prolog
prolog
prolog
true.

 

Exemple 4 de la coupure : se limiter à la première réponse dans le cas de réponses multiples

Nous retrouvons un arbre généalogique très simple : jean est le père de 3 enfants :

pere(jean,luc). % jean est le père de luc
pere(jean,remi). % jean est le père de rémi
pere(jean,laurent). % jean est le père de laurent

Posons quelques questions à l'interpréteur avec ou sans coupure :

Qui est le père de laurent ? Réponse : jean :

?- pere(X,laurent).
X = jean.

Qui est le fils de jean (qui a pour père jean) ? Réponse : jean a 3 fils luc, rémi et laurent, il y a donc 3 solutions :

?- pere(jean,X).
X = luc ;
X = remi ;
X = laurent.

Rémi a-t-il un père ? Réponse : oui :

?- pere(_,remi).
true.

Jean est-il un père ? Et là encore la réponse est triple puisque l'interpréteur a trouvé 3 fois la réponse à la question :

?- pere(jean,_).
true ;
true ;
true.

Si on veut juste savoir si Jean est un père ou pas, peut importe le nombre de fils. Dans ce cas on va poser la question en utilisant la coupure afin de s'arrêter dès la premère réponse positive :

?- pere(jean,_),!.
true.

Ainsi l'interpréteur arrête sa recherche dès le premier fils trouvé, sans perdre de temps à se demander si jean a d'autres fils, ce qui n'a aucune importance pour répondre à la question "Jean est-il un père ?".

De même, si on pose la question "Qui sont les fils de jean ?" avec une coupure à la fin, l'interpréteur arrêtera la recherche dès la première solution trouvée :

?- pere(jean,X),!.
X = luc.

La question précédente peut alors se formuler ainsi : "Donnez-moi un fils de jean et un seul, peu importe lequel".

 

Retour en haut de la page

 

Exemple 5 : génération des grilles de roulement des TP tournants

Le problème à résoudre (qui est réel ...) est le suivant :

Les 15 élèves sont identifiés chacun par une lettre unique (de A à O).

Voici un exemple de grille de roulement correspondant à ce problème (il ne s'agit que d'un exemple parmi un très grand nombre) :

Séance 1
Séance 2
Séance 3
Séance 4
Séance 5
TP 1
A F K
E G M
D H O
C I L
B J N
TP 2
B G L
A H N
E I K
D J M
C F O
TP 3
C H M
B I O
A J L
E F N
D G K
TP 4
D I N
C J K
B F M
A G O
E H L
TP 5
E J O
D F L
C G N
B H K
A I M

J'ai obtenu le tableau ci-dessus en faisant tourner 3 disques cocentriques en carton, découpés chacun en 5 secteurs angulaires, et avec une lettre dans chacun des secteurs angulaires : un disque reste fixe, le second tourne dans un sens, et le troisième tourne dans l'autre sens. Malheureusemnet les 5 élèves inscrits sur le même disque ne se rencontreront jamais (A, B, C, D et E par exemple ne seront jamais ensemble : ils appartiennent toujours à la première colonne de lettre, et ce à chaque séance).

Mais l'objectif est ici de jeter les disques en carton (qui ne donnent même pas une solution satisfaisante comme décrit précédemment) et de généraliser le problème à une classe possédant un nombre quelconque d'élèves multiple de 3 (9, 12, 15, 18, 21, 24 ou 30 élèves).

Comment programmer en Prolog la génération d'une telle grille de roulement ?

Voici une première solution qui impose certaines conditions (mais même pas l'interdiction de recréer les mêmes groupes de 3). L'inconvénient d'un tel programme c'est qu'il faut plusieurs heures à Prolog pour sortir la première grille ...

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des grilles de roulement des TP en Prolog %
% Réalisé par Jean-Christophe MICHEL                   %
% Novembre 2012                                        %
% www.gecif.net                                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% appel récursif si la liste à afficher contient plusieurs éléments :
afficher_liste([X|L]) :- writeln(X), afficher_liste(L).
% affiche un séparateur si la liste ne contient plus qu'un seul élément :
afficher_liste([]) :- writeln('appuyer sur ; pour continuer ou sur . pour terminer'),put(7).

app(X,L) :- append(_,[X|_],L).

complet(L):-app(a,L),
app(b,L),
app(c,L),
app(d,L),
app(e,L),
app(f,L),
app(g,L),
app(h,L),
app(i,L),
app(j,L),
app(k,L),
app(l,L),
app(m,L),
app(n,L),
app(o,L).

resoudre :-
T1S1=[a,f,k],
T1S2=[e,g,m],
T1S3=[d,h,o],
T1S4=[c,i,l],
T1S5=[b,j,n],

T2S1=[b,g,l],
T2S2=[_,_,_],
T2S3=[_,_,_],
T2S4=[_,_,_],
T2S5=[_,_,_],

T3S1=[c,h,m],
T3S2=[_,_,_],
T3S3=[_,_,_],
T3S4=[_,_,_],
T3S5=[_,_,_],

T4S1=[d,i,n],
T4S2=[_,_,_],
T4S3=[_,_,_],
T4S4=[_,_,_],
T4S5=[_,_,_],

T5S1=[e,j,o],
T5S2=[_,_,_],
T5S3=[_,_,_],
T5S4=[_,_,_],
T5S5=[_,_,_],

GRILLE = [TP1,TP2,TP3,TP4,TP5],

% on "met à plat" les 5 listes représentant les lignes du tableau :
flatten([T1S1,T1S2,T1S3,T1S4,T1S5], TP1),
flatten([T2S1,T2S2,T2S3,T2S4,T2S5], TP2),
flatten([T3S1,T3S2,T3S3,T3S4,T3S5], TP3),
flatten([T4S1,T4S2,T4S3,T4S4,T4S5], TP4),
flatten([T5S1,T5S2,T5S3,T5S4,T5S5], TP5),

% on "met à plat" les 5 listes représentant les colonnes du tableau :
flatten([T1S1,T2S1,T3S1,T4S1,T5S1], SEANCE1),
flatten([T1S2,T2S2,T3S2,T4S2,T5S2], SEANCE2),
flatten([T1S3,T2S3,T3S3,T4S3,T5S3], SEANCE3),
flatten([T1S4,T2S4,T3S4,T4S4,T5S4], SEANCE4),
flatten([T1S5,T2S5,T3S5,T4S5,T5S5], SEANCE5),

% on vérifie qu'a chaque TP il y a une seule fois chaque eleve :
complet(TP1),
complet(TP2),
complet(TP3),
complet(TP4),
complet(TP5),

% on vérifie qu'a chaque seance il y a une seule fois chaque eleve :
complet(SEANCE1),
complet(SEANCE2),
complet(SEANCE3),
complet(SEANCE4),
complet(SEANCE5),

afficher_liste(GRILLE),!.

Voici une variante utilisant le prédicat prédéfini permutation de swi-prolog à la place du prédicat complet :

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des grilles de roulement des TP en Prolog %
% Réalisé par Jean-Christophe MICHEL                   %
% Novembre 2012                                        %
% www.gecif.net                                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% appel récursif si la liste à afficher contient plusieurs éléments :

afficher_liste([X|L]) :- writeln(X), afficher_liste(L).
% affiche un séparateur si la liste ne contient plus qu'un seul élément :
% put(7) à la fin permet de sonner dès la première solution trouvée

afficher_liste([]) :- writeln('appuyer sur ; pour continuer ou sur . pour terminer'),put(7).

% pour limiter l'espace de recherche on a rempli au hasard le TP1 et la SEANCE1 :
resoudre :-
T1S1=[a,b,c],
T1S2=[d,n,j],
T1S3=[e,g,k],
T1S4=[f,h,l],
T1S5=[m,i,o],

T2S1=[d,e,f],
T2S2=[_,_,_],
T2S3=[_,_,_],
T2S4=[_,_,_],
T2S5=[_,_,_],

T3S1=[g,h,i],
T3S2=[_,_,_],
T3S3=[_,_,_],
T3S4=[_,_,_],
T3S5=[_,_,_],

T4S1=[j,k,l],
T4S2=[_,_,_],
T4S3=[_,_,_],
T4S4=[_,_,_],
T4S5=[_,_,_],

T5S1=[m,n,o],
T5S2=[_,_,_],
T5S3=[_,_,_],
T5S4=[_,_,_],
T5S5=[_,_,_],

GRILLE = [TP1,TP2,TP3,TP4,TP5],

% on "met à plat" les 5 listes représentant les lignes du tableau :
flatten([T1S1,T1S2,T1S3,T1S4,T1S5], TP1),
flatten([T2S1,T2S2,T2S3,T2S4,T2S5], TP2),
flatten([T3S1,T3S2,T3S3,T3S4,T3S5], TP3),
flatten([T4S1,T4S2,T4S3,T4S4,T4S5], TP4),
flatten([T5S1,T5S2,T5S3,T5S4,T5S5], TP5),


% on "met à plat" les 5 listes représentant les colonnes du tableau : flatten([T1S1,T2S1,T2S1,T3S1,T4S1,T5S1], SEANCE1),
flatten([T1S2,T2S2,T2S2,T3S2,T4S2,T5S2], SEANCE2),
flatten([T1S3,T2S3,T2S3,T3S3,T4S3,T5S3], SEANCE3),
flatten([T1S4,T2S4,T2S4,T3S4,T4S4,T5S4], SEANCE4),
flatten([T1S5,T2S5,T2S5,T3S5,T4S5,T5S5], SEANCE5),

% on vérifie qu'a chaque TP il y a une seule fois chaque eleve :
permutation(TP1, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(TP2, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(TP3, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(TP4, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(TP5, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),

% on vérifie qu'a chaque seance il y a une seule fois chaque eleve :
permutation(SEANCE1, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(SEANCE2, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(SEANCE3, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(SEANCE4, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),
permutation(SEANCE5, [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o]),

afficher_liste(GRILLE).

Et voici une troisième solution (avec une classe de 9 élèves seulement pour accélérer la recherche) :

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des grilles de roulement des TP en Prolog %
% Réalisé par Jean-Christophe MICHEL                   %
% Novembre 2012                                        %
% www.gecif.net                                        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% appel récursif si la liste à afficher contient plusieurs éléments :

afficher_liste([X|L]) :- writeln(X), afficher_liste(L).
% affiche un séparateur si la liste ne contient plus qu'un seul élément :
afficher_liste([]) :- writeln('appuyer sur ; pour continuer ou sur . pour terminer'),put(7).

% app(X,L) est vrai si X appartient à la liste L
app(_,[]):-!,fail.
app(X,[X|_]).
app(X,[_|L]):-app(X,L).

% diff(L1,L2,L3) est vrai si la liste L3 est la liste L1 privée des éléments présents dans L2
diff([],_,[]).
diff([X|L],M,R):- app(X,M),!,diff(L,M,R).
diff([X|L],M,[X|R]):- diff(L,M,R).

% egaux(L1,L2) est vrai si les deux listes L1 et L2 sont égale en tant qu'ensemble,
% c'est-à-dire sans tenir compte de l'ordre ou des répétitions

egaux(L,M):-diff(L,M,[]),diff(M,L,[]).

% non(true) donne fail, et non(fail) donne true
non(P):-P,!,fail.
non(_).

complet(L):-app(a,L),
app(b,L),
app(c,L),
app(d,L),
app(e,L),
app(f,L),
app(g,L),
app(h,L),
app(i,L).

% pour limiter l'espace de recherche on a déjà rempli le TP1 :
resoudre :-
T1S1=[a,b,c],
T1S2=[d,e,f],
T1S3=[g,h,i],

T2S1=[_,_,_],
T2S2=[_,_,_],
T2S3=[_,_,_],

T3S1=[_,_,_],
T3S2=[_,_,_],
T3S3=[_,_,_],

% aucun des 3 groupes du TP2 ne doit être égal à un des groupes du TP1
non(egaux(T2S1,T1S1)),
non(egaux(T2S1,T1S2)),
non(egaux(T2S1,T1S3)),

non(egaux(T2S2,T1S1)),
non(egaux(T2S2,T1S2)),
non(egaux(T2S2,T1S3)),

non(egaux(T2S3,T1S1)),
non(egaux(T2S3,T1S2)),
non(egaux(T2S3,T1S3)),

GRILLE = [TP1,TP2,TP3],

% flatten met à plat la première liste composée dans la seconde
flatten([T1S1,T1S2,T1S3], TP1),
flatten([T2S1,T2S2,T2S3], TP2),
flatten([T3S1,T3S2,T3S3], TP3),

flatten([T1S1,T2S1,T3S1], SEANCE1),
flatten([T1S2,T2S2,T3S2], SEANCE2),
flatten([T1S3,T2S3,T3S3], SEANCE3),

% on vérifie qu'a chaque TP il y a une seule fois chaque eleve :
complet(TP1),
complet(TP2),
complet(TP3),

% on vérifie qu'a chaque seance il y a une seule fois chaque eleve :
complet(SEANCE1),
complet(SEANCE2),
complet(SEANCE3),

% la coupure à la fin permet de s'arrêter dès la première grille trouvée
afficher_liste(GRILLE),!.

Mais malheureusement aucune de ces 3 solutions n'est fonctionnelle puisqu'il faut plusieurs heures à Prolog pour trouver une solution, sans que l'on soit sûr qu'il ne va pas sortir false après un jour de calcul ou qu'il ne va pas répéter les mêmes groupes dans les 5 séances ...

 

Et voici une première solution fonctionnelle utilisant les modules lambda et clpfd de Prolog et donnant une grille en moins de 2 minutes :

Télécharger le module lambda.pl qui n'est pas inclus dans SWI-Prolog (fichier à enregistrer dans le répertoire C:\Program Files\pl\library)

:- use_module(library(lambda)).
:- use_module(library(clpfd)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des grilles de roulement des TP en Prolog %
% Janvier 2015       
                                  %

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% détails des séances
% 5 TP (donc 5 séances) avec 3 élèves à chaque TP
details(5, 3).

solve :-
    details(TP, PTP),

    % L est une liste de TP séances
    % L = [Si]
    % Chaque séance est une liste de TP TPs
    % Si = [Tpi]
    % Chaque TP est une liste de PTP élèves
    % TPi = [Ei]

    % nombre d'élèves
    % les elèves sont numérotés de 1 à Eleves
    Eleves is TP * PTP,

    % le nombre de séances est le même que celui des TP
    Se = TP,

    % on crée la liste des séances de longueur Se
    length(L, Se),

    % on crée la liste des TP pour chaque séance
    maplist(\X^T^(length(X, TP),
        % chaque TP est une liste de PTP élèves
        maplist(\Y^V^(length(Y, PTP),
            % Les élèves sont choisis parmi Eleves élèves
            Y ins 1..Eleves,
            % ils sont évidemment différents
            all_distinct(Y),
            % Pour une lecture plus simple des résultats
            % les élèves sont rangés par ordre de numéro
            chain(Y, #<),
            % ici on attribue des clés aux combinaisons d'élèves
            % 2 élèves ne peuvent pas travailler 2 fois ensemble
            calcule_cles(Y, [], V)),
            X, T)),
        L, D),
    % on récupère la liste des clés
    % et on déclare que toutes les clés sont différentes
    flatten(D, FD),
    all_distinct(FD),

    % il ne reste plus qu'à imposer les contraintes de participation aux séances de TP
    contraintes_cours(L, TP),
    flatten(L, FL),

    % on demande à SWI-Prolog de calculer les résultats
    % on peut tester différentes combinaisons d'options de labeling
    labeling([ffc, bisect], FL),

    % affichage des résultats
    maplist(writeln, L).

calcule_cles([], Lst, Lst).

%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Prédicat calcule_cles :

calcule_cles([H | T], Cur, Lst) :-
    maplist(H +\X^Y^(Y #= 100 * H + X), T, R),
    append(Cur, R, Cur1),
    calcule_cles(T, Cur1, Lst).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Prédicat contraintes_cours(L,TP) :

contraintes_cours(L, TP) :-
    % la contrainte sur les cours est que tous les elèves soient en TP
    maplist(\X^(flatten(X, FX), all_distinct(FX)), L),
    % tous les élèves doivent participer à tous les TP
    numlist(1,TP, NL),
    maplist(L +\Y^(foldl(\U^V^W^(nth1(Y, U, Row),
        append(V, Row, W)),
        L, [], TPS),
        all_distinct(TPS)),
    NL).

Voici la grille générée en 100 secondes seulement avec les options labeling([ffc, bisect], FL) :

3 ?- time(solve).
[[1,2,11],[3,4,12],[5,6,13],[7,8,14],[9,10,15]]
[[3,5,7],[13,14,15],[8,10,11],[2,9,12],[1,4,6]]
[[4,8,15],[5,9,11],[1,12,14],[3,6,10],[2,7,13]]
[[6,9,14],[1,7,10],[2,3,15],[4,11,13],[5,8,12]]
[[10,12,13],[2,6,8],[4,7,9],[1,5,15],[3,11,14]]
% 256,073,985 inferences, 97.922 CPU in 99.969 seconds (98% CPU, 2615085 Lips)
true

Et voici une autre grille générée cette fois avec les options labeling([ff, enum], FL) :

1 ?- time(solve).
[[1,6,11],[2,7,12],[3,8,13],[4,9,14],[5,10,15]]
[[2,3,4],[13,14,15],[9,10,11],[5,6,12],[1,7,8]]
[[5,8,14],[1,4,10],[2,6,15],[7,11,13],[3,9,12]]
[[7,9,15],[3,5,11],[1,12,14],[2,8,10],[4,6,13]]
[[10,12,13],[6,8,9],[4,5,7],[1,3,15],[2,11,14]]
% 416,780,793 inferences, 157.844 CPU in 160.906 seconds (98% CPU, 2640464 Lips)
true ;

Si on a un groupe de 12 élèves seulement travaillant toujours par 3 et qu'on a 4 TP à faire en 4 séances on configure details(4, 3) dans le programme puis Prolog nous sort la grille pour 12 élèves en moins de 30 secondes (avec les options labeling([ffc, bisect], FL)) :

1 ?- time(solve).
[[1,2,9],[3,4,10],[5,6,11],[7,8,12]]
[[3,5,7],[1,6,12],[2,8,10],[4,9,11]]
[[4,6,8],[2,7,11],[3,9,12],[1,5,10]]
[[10,11,12],[5,8,9],[1,4,7],[2,3,6]]
% 56,568,677 inferences, 21.531 CPU in 21.875 seconds (98% CPU, 2627283 Lips)
true

Et voici une autre grille générée cette fois avec les options labeling([ff, enum], FL) :

1 ?- time(solve).
[[1,5,9],[2,6,10],[3,7,11],[4,8,12]]
[[2,3,4],[1,7,12],[5,8,10],[6,9,11]]
[[6,7,8],[4,5,11],[2,9,12],[1,3,10]]
[[10,11,12],[3,8,9],[1,4,6],[2,5,7]]
% 37,017,359 inferences, 14.281 CPU in 14.563 seconds (98% CPU, 2592025 Lips)
true ;

Mais malheureusement le programme ci-dessus n'arrive pas à sortir une grille de roulement pour un groupe de 18 élèves travaillant par 3 durant 6 séances. Si on lance le programme avec details(6, 3) SWI-Prolog calcule durant des heures sans sortir de grille ni planter. Au bout de 12 heures de calcul avec details(6, 3) SWI-Prolog n'a toujours pas sorti de grille (alors qu'il met seulement 15 secondes pour 12 élèves et 100 secondes pour 15 élèves ...). L'objectif de généraliser le problème à tous les groupes d'élèves multiples de 3 n'est donc toujours pas atteint. Mais pourquoi ? Mystère ! :-)

Mais le programme ci-dessus nous permet tout de même de découvrir 10 nouveaux prédicats, principalement pour la manipulation des listes.

Explications concernant les 10 nouvelles fonctions (ou prédicats, ou opérateurs, ...) utilisées dans ce programme et qui n'ont jamais été utilisées dans les exemples précédents :

Les 5 fonctions natives de SWI-Prolog length, nth1, numlist, flatten et maplist :

length(L,N) retourne true si L est une liste composée de N éléments (donne à N la taille de L afin d'être vrai). Exemple :

1 ?- length([1,2,3,4,5],X).
X = 5.

nth1(N,L,X) retourne true si la liste L possède l'élément X à la position N. Exemple :

1 ?- nth1(2,[7,9,12,45],9).
true.

2 ?- nth1(3,[7,9,12,45],9).
false.

3 ?- nth1(1,L,9),nth1(2,L,8),nth1(3,L,7),length(L,3).
L = [9, 8, 7].

numlist(MIN,MAX, L) crée une liste numérique L composée des entiers allant de MIN à MAX. Exemple :

1 ?- numlist(2,9,L).
L = [2, 3, 4, 5, 6, 7, 8, 9].

flatten(L1,L2) applanit et unifie une liste composée L1. L1 peut contenir de nombreuses listes imbriquées récursivement. flatten extrait tous les éléments contenus dans L1 et stoque le résultat dans une liste "plane" L2 (à une seule dimension). Exemple :

1 ?- flatten([[1,[2],3], [[4,5],[6,7]]], L).
L = [1, 2, 3, 4, 5, 6, 7].

2 ?- flatten([[1], [2,3,4,5]], L).
L = [1, 2, 3, 4, 5]

Remarque : flatten applanit une liste composée mais ne suprime pas les doublons :

3 ?- flatten([[1,[2],[1,3]], [[2,1],[1,2]]], L).
L = [1, 2, 1, 3, 2, 1, 1, 2].

maplist(P,L) applique le prédicat P sur chaque élément de la liste L. Exemple :

1 ?- maplist(writeln,[1,2,3,4,5]).
1
2
3
4
5
true.

Ci-dessous X prend à tour de rôle chacune des sous-listes de la liste composée, et le prédicat \X^(all_distinct(X)) répond true si tous les éléments de la sous-liste X sont différents :

2 ?- maplist(\X^(all_distinct(X)), [[1,2],[3,4]]).
true.

3 ?- maplist(\X^(all_distinct(X)), [[1,2],[3,3]]).
false.

4 ?- maplist(\X^(all_distinct(X)), [[1,2],[3,2]]).
true.

De manière générale maplist(P,L) est true si la prédicat P est true pour chacun des éléments de la liste L. L'exemple suivant vérifie que tous les éléments d'une liste sont inférieurs à 5 :

5 ?- maplist(\X^(X#<5), [1,2,3,4]).
true.

6 ?- maplist(\X^(X#<5), [1,2,3,6]).
false.

Et si on passe en paramètre 2 listes à maplist(P,L1,L2) le prédicat P reçoit à chaque appel 2 paramètres : les éléments de même rang pris dans les listes L1 et L2. Dans la syntaxe \X^Y^(...) du prédicat chaque paramètre est séparé des autres par un caractères ^ et le code du prédicat est écrit entre les paranthèses. Dans cet exemple les 2 paramètres reçu par le prédicat s'appellent X et Y, et le prédicat \X^Y^(write(X),write(' '),writeln(Y)) se contente de les afficher :

7 ?- maplist(\X^Y^(write(X),write(' '),writeln(Y)), [1,2,3,4],[5,6,7,8]).
1 5
2 6
3 7
4 8
true.

L'exemple suivant fabrique une liste L en multipliant par 3 chaque élément de la liste initiale :

8 ?- maplist(\X^Y^(Y is 3*X), [1,2,3,4],L).
L = [3, 6, 9, 12].

L'exemple suivant montre comment composer une 3ème liste à partir de deux autres : chaque élément de la liste L est la somme des 2 éléments de même rang dans les autres liste (ce qui peut correspondre au calcul de la somme de deux vecteurs). On passe en paramètre à maplist 3 listes, et les paramètres X Y et Z du prédicat représentent un élément de même rang dans chacune des listes à chaque appel :

9 ?- maplist(\X^Y^Z^(Z is X+Y), [1,2,3,4],[5,6,7,8],L).
L = [6, 8, 10, 12].

Et à partir des deux listes initiales précédentes l'exemple suivant génère 2 nouvelles listes : une "liste somme" L1 et une "liste produit" L2 :

10 ?- maplist(\W^X^Y^Z^(Y is W+X,Z is W*X), [1,2,3,4],[5,6,7,8],L1,L2).
L1 = [6, 8, 10, 12],
L2 = [5, 12, 21, 32].

On peut donc passer en paramètre à maplist autant de listes qu'on veut, et le prédicat appelé pour chaque élément de même rang des listes doit avoir autant de paramètres qu'il y a de listes.

 

Les 5 fonctions disponibles seulement après avoir inclus les modules lambda et clpfd : all_distinct, chain, ins, labeling et foldl :

:- use_module(library(lambda)).
:- use_module(library(clpfd)).

Le modules clpfd contient les prédicats suivants : all_distinct/1    chain/2   (ins)/2   et   labeling/2

Par défaut SWI-Prolog contient les prédicats foldl/4   foldl/5   foldl/6   et   foldl/7

Le modules lambda permet de définir directement des prédicats avec passage de paramètres en utilisant la syntaxe \X^Y^Z^(action)

all_distinct(L) retourne true si tous les éléments de la liste L sont différents. Exemple :

1 ?- all_distinct([1,2,3]).
true.

2 ?- all_distinct([1,2,2]).
false.

chain(L, #<) retourne true si les nombres de la liste numérique L sont rangés dans l'ordre croissant. Exemple :

1 ?- chain([1,2,3],#<).
true.

2 ?- chain([1,4,3],#<).
false.

L ins MIN..MAX retourne true si tous ses éléments de la liste numérique L sont compris dans l'intervale MIN..MAX. Exemples :

1 ?- [1,2,3] ins 1..3.
true.

2 ?- [1,2,3] ins 1..8.
true.

3 ?- [1,2,3] ins 5..8.
false.

4 ?- [6,7] ins 5..8.
true.

5 ?- [6,7,8] ins 7..9.
false.

labeling([ffc, bisect], L) : oriente Prolog vers une méthode ou une autres dans le choix des variables lorsque plusieurs solutions sont possibles. Exemple : labeling([ff, enum], L) ou labeling([], L)

foldl(P,L,A,B) : appelle le prédicat P autant de fois que le nombre d'éléments de la liste L en lui passant 3 paramètres, le premier paramètre étant à tour de rôle chaque élément de la liste L :

1 ?- foldl(\X^Y^Z^(write('X='),write(X),write(' Y='),write(Y),write(' Z='),writeln(Z)), [1,2,3],4,5).
X=1 Y=4 Z=_G4202
X=2 Y=_G4202 Z=_G4248
X=3 Y=_G4248 Z=_G4294
true.

L'exemple suivant montre comment calculer la somme de tous les éléments d'une liste grâce à foldl :

2 ?- foldl(\X^Y^Z^(Z is Y+X), [1,2,3,4], 0, R).
R = 10.

Voici pour l'exemple précédent l'évolution des 4 variables à chaque appel du prédicat (0 est la valeur initiale de Y et R est le résultat final) :

3 ?- foldl(\X^Y^Z^(write('X='),write(X),write(' Y='),write(Y),write(' Z='),write(Z),write(' R='),writeln(R),Z is Y+X), [1,2,3,4], 0, R).
X=1 Y=0 Z=_G2399 R=_G2432
X=2 Y=1 Z=_G2462 R=_G2495
X=3 Y=3 Z=_G2525 R=_G2558
X=4 Y=6 Z=_G2588 R=_G2621
R = 10.

Voici quelques programmes écrits dans d'autres langage que Prolog permettant de générer ces grilles de roulement de TP :

Génération d'une grille pour 12 élèves en Perl en simulant la rotation des disques en carton :

# Permutations circulaires des valeurs dans un tableau :
# Génération d'une grille de roulement pour 12 élèves
# Programme réalisé le 10 février 2015

# Configuration des 3 disques divisé chacun en 4 secteurs angulaires :
@t1=("A","B","C","D");
@t2=("E","F","G","H");
@t3=("I","J","K","L");

for ($i=0;$i<4;$i++)
{
      for ($j=0;$j<4;$j++)
      {
            printf "$t1[$j] $t2[$j] $t3[$j] ";
      }
      printf "\n";
      
# Rotation du disque 1 d'1 secteur dans le sens 1 :
          ($t1[0],$t1[1],$t1[2],$t1[3])=($t1[3],$t1[0],$t1[1],$t1[2]);
      
# Rotation du disque 2 d'1 secteur dans le sens 2 :
      ($t2[0],$t2[1],$t2[2],$t2[3])=($t2[1],$t2[2],$t2[3],$t2[0]);
      
# Rotation du disque 3 de 2 secteurs dans le sens 2 :
      ($t3[0],$t3[1],$t3[2],$t3[3])=($t3[2],$t3[3],$t3[0],$t3[1]);
}

Résultat obtenu :

A E I       B F J       C G K       D H L
D F K       A G L       B H I       C E J
C G I       D H J       A E K       B F L
B H K       C E L       D F I       A G J

Génération d'une grille pour 15 élèves en Perl en simulant la rotation des disques en carton :

# Permutations circulaires des valeurs dans un tableau :
# Génération d'une grille de roulement pour 15 élèves
# Programme réalisé le 10 février 2015

# Configuration des 3 disques divisé chacun en 5 secteurs angulaires :
@t1=("A","B","C","D","E");
@t2=("F","G","H","I","J");
@t3=("K","L","M","N","O");

for ($i=0;$i<5;$i++)
{
      for ($j=0;$j<5;$j++)
      {
            printf "$t1[$j] $t2[$j] $t3[$j] ";
      }
      printf "\n";
      
# Rotation du disque 1 d'1 secteur dans le sens 1 :
      ($t1[0],$t1[1],$t1[2],$t1[3],$t1[4])=($t1[4],$t1[0],$t1[1],$t1[2],$t1[3]);
      
# Rotation du disque 2 d'1 secteur dans le sens 2 :
      ($t2[0],$t2[1],$t2[2],$t2[3],$t2[4])=($t2[1],$t2[2],$t2[3],$t2[4],$t2[0]);
      
# Rotation du disque 3 de 2 secteurs dans le sens 2 :
      ($t3[0],$t3[1],$t3[2],$t3[3],$t3[4])=($t3[2],$t3[3],$t3[4],$t3[0],$t3[1]);
}

Résultat obtenu :

A F K       B G L       C H M       D I N       E J O
E G M       A H N       B I O       C J K       D F L
D H O       E I K       A J L       B F M       C G N
C I L       D J M       E F N       A G O       B H K
B J N       C F O       D G K       E H L       A I M

Transformation du problème des grilles de roulement en un problème SAT

Génération d'une grille pour 18 élèves en Python en utilisant le SAT Solver minisat qui résoud des problèmes SAT (problème de satisfaisabilité booléenne modélisé par une équation logique à forme normale conjonctive : CNF en anglais pour Conjunctive Normal Form). Exemple d'équation logique CNF modélisant un problème SAT : (x1+x2+/x3).(x1+/x2).(/x1+x2+x3)

x1, x2 et x3 sont dans cet exemple les 3 variables booléennes du problème. Le rôle de minisat est de trouver une valeur (0 ou 1) pour chacune des 3 variables x1 x2 et x3 de telle sorte que l'équation CNF soit vraie (égale à 1).

Le programme en Python suivant ne résoud pas directement le problème des grilles de roulement : il génère un fichier texte nommé gen au format dimacs (description de l'équation logique CNF au format minisat) puis appelle le solver minisat qui trouve une solution et l'écrit dans le fichier nommé out. Ensuite le programme Pyton ouvre et interprète le fichier de sortie out produit par minisat pour présenter la grille de roulement sur sa sortie standard.

Le travail effectué par ce programme Python est de convertir le problème des grilles de roulement en un problème SAT en le modélisant sous la forme d'une équation logique à forme normale conjonctive (plusieurs termes en OU reliés par des ET).

# Génération d'une grille de roulement pour 18 élèves
# en utilisant le solver minisat
# Février 2015

import itertools
import os

PARSEOUTPUT=True

#There are 6 sessions, s in [1,6].
#There are 6 practicals, p in [1,6].
#There are 18 students, y in [1,18].
NSTUDENTS = 18
NPRACTICALS = 6
NSESSIONS = 6

sessions = range(NSESSIONS)
practicals = range(NPRACTICALS)
students = range(NSTUDENTS)

# setup different selections
ij_pairs = [(i,j) for i in students for j in range(i+1, NSTUDENTS)]
ijkl_tuples = [(i,j,l,k)
      for i in students
      for j in range(i+1, NSTUDENTS)
      for k in range(j+1, NSTUDENTS)
      for l in range(k+1, NSTUDENTS)]

groups = [(s,p) for s in sessions for p in practicals]
practical_pairs = [(p,p_prime)
      for p in practicals
      for p_prime in range(p+1, NPRACTICALS)]
session_pairs = [(s,s_prime)
      for s in sessions
      for s_prime in range(s+1, NSESSIONS)]

print( len(ij_pairs), len(ijkl_tuples), len(groups), len(practical_pairs), len(session_pairs))

# allocate all of the variables
variables=itertools.count(1,1)

# In each session, a student is assigned into a practical.
# The set of students assigned into the same practical and session is a group.

# x_{s,p,i} student i is in session s and practical p [648]
# y_{s,p,i,j} students i and j (i < j) is in session s and practical p [6426]

xs = dict()
reverse_xs = dict()
for s in sessions:
      for p in practicals:
            for i in students:
                  xs[(s,p,i)] = variables.next()
                  reverse_xs[xs[(s,p,i)]] = (s,p,i)
def x(s,p,i):
      return xs[(s,p,i)]

ys = dict()
reverse_ys = dict()
for s in sessions:
      for p in practicals:
            for i,j in ij_pairs:
                  ys[(s,p,i,j )] = variables.next()
                  reverse_ys[ys[(s,p,i,j)]] = (s,p,i,j)
def y(s,p,i,j):
      return ys[(s,p,i,j)]

numvariables = variables.next()

clauses = []
#% Define each y_{s,p,i,j} [6426, 2] [6426, 2], [6426, 3]
# forall_{s,p,i<j} y_{s,p,i,j} => x_{s,p,i}
# forall_{s,p,i<j} y_{s,p,i,j} => x_{s,p,j}
# forall_{s,p,i<j} or(~x_{s,p,i}, ~x_{s,p,j}, y_{s,p,i,j})
for s, p in groups:
      for i,j in ij_pairs:
            clauses.append( [-y(s,p,i,j), x(s,p,i)])
            clauses.append( [-y(s,p,i,j), x(s,p,j)])
            clauses.append( [-x(s,p,i), -x(s,p,j), y(s,p,i,j)])


print (len(clauses))

# % Each group is >= 2 distinct students [36, 153]
# forall_{s,p} exists_{i < j} y_{s,p,i,j}
for s, p in groups:
      c = [y(s,p,i,j) for (i,j) in ij_pairs]
      clauses.append(c)

print (len(clauses))

# % each group is >= 3 distinct students [5508, 16+1]
# forall_{s,p,i,j} y_{s,p,i,j} => exists_{k!=i and k!=j} x_{s,p,k}
for s, p in groups:
      for i,j in ij_pairs:
            c = [-y(s,p,i,j)]
            for k in students:
                  if k != i and k != j:
                        c.append(x(s,p,k))
            clauses.append(c)
print (len(clauses))

# % each group is < 4 [110160, 4]
# forall_{s,p,i<j<k<l} not( and(x_{s,p,i},x_{s,p,j},x_{s,p,k},x_{s,p,l}))
for s,p in groups:
      for i,j,k,l in ijkl_tuples:
            c= [-x(s,p,i),-x(s,p,j),-x(s,p,k),-x(s,p,l) ]
            clauses.append(c)

print (len(clauses))

# % all the students must participate in every session [108, 6]
# forall_{s,i} exists_{p} x_{s,p,i}

for s in sessions:
      for i in students:
            c = [x(s,p,i) for p in practicals]
            clauses.append(c)
print (len(clauses))

# % all the students must participate in every practical [108, 6]
# forall_{p,i} exists_{s} x_{s,p,i}
for p in practicals:
      for i in students:
            c = [x(s,p,i) for s in sessions]
            clauses.append(c)

print (len(clauses))

# % no student participates in two practicals in the same session [1620, 2]
# forall_{i,s,p<p'} not(and(x_{s,p,i}, x_{s,p',i}))
for s in sessions:
      for i in students:
            for p,p_prime in practical_pairs:
                  c = [-x(s,p,i),-x(s,p_prime,i)]
                  clauses.append(c)

print (len(clauses))

# % no student participates twice in the same practical in different sessions [1620, 2]
# forall_{i,p, s<s'} not(and(x_{s,p,i}, x_{s',p,i}))
for p in practicals:
      for i in students:
            for s,s_prime in session_pairs:
                  c= [-x(s,p,i),-x(s_prime,p,i)]
                  clauses.append(c)

print (len(clauses))

# % Two students are in the same group most once [34425, 2]
# forall_{s<s',p<p',i<j} (not y_{s,p,i,j} or not y_{s',p',i,j})
for i,j in ij_pairs:
      for p,p_prime in practical_pairs:
            for s,s_prime in session_pairs:
                  c= [-y(s,p,i,j), -y(s_prime,p_prime,i,j)]
                  clauses.append(c)
                  c= [-y(s_prime,p,i,j), -y(s,p_prime,i,j)]
                  clauses.append(c)

print (len(clauses))

# prépare le fichier gen qui sera transmis à minisat :

print ('p cnf ', numvariables, len(clauses))
with open("gen", "w") as f:
      f.write('p cnf ' + str( variables.next() ) +' '+ str( len(clauses))+'\n')
      for c in clauses:
            f.write( " ".join(map(lambda x: str(x),c)))
            f.write( " 0\n")

# execute
# minisat gen out
# Appel du solver minisat en lui passant en paramètre le fichier gen :
os.system('minisat gen out')

if PARSEOUTPUT:
      # lit le fichier out généré par minisat :
      with open("out", "r") as f:
            lines = list(f)
            assert len(lines) == 2
            assert lines[0] == "SAT\n"
            assignments = lines[1].split(" ")
            positives = []
            for literal in assignments:
                  lit = int(literal)
                  if lit in reverse_xs and lit > 0:
                        (s,p,i) = reverse_xs[lit]
                        positives.append((i,s,p))

            for s in sessions :
                  chars = list()
            for p in practicals :
                  for k in students :
                        if (k,s,p) in positives :
                              chars.append("%2d " %(k+1))

                  chars.append('\t')
            print("".join(chars))

Résultat obtenu :

13 15 17       10 11 12        2  4 18        3  6  7        5  8 16        1  9 14
 3 16 18
       2 14 15        5  6 11        1  8 12        9 10 13        4  7 17
 5
 9 12        1 16 17        7 10 15       11 13 18        4  6 14        2  3  8
 7 11 14
       3  4  5        8  9 17        2 10 16        1 15 18        6 12 13
 1
 2  6        7  8 13       12 14 16        4  9 15        3 11 17        5 10 18
 4
 8 10        6  9 18        1  3 13        5 14 17        2  7 12       11 15 16

 

Retour en haut de la page

 

Exemple 6 : génération des combinaisons d'une liste sans doublons

Le problème à résoudre est le suivant : on dispose d'une liste de N éléments, et on veut toutes les listes de K éléments pris dans la liste d'origine et sans notion d'ordre. Exemple :

On veut toutes les listes à 3 éléments pris dans la liste à 5 éléments [a, b, c, d, e]. La solution recherchée est :

[a, b, c]
[a, b, d]
[a, b, e]
[a, c, d]
[a, c, e]
[a, d, e]
[b, c, d]
[b, c, e]
[b, d, e]
[c, d, e]

Ces 10 listes sont bien uniques en considérant que [a, b, c] et [a, c, b] sont identiques : la liste [a, b, c] n'est pas suivi de toutes ses permutations.

Première solution simple : on demande toutes les permutations de la liste [a, b, c, d, e] et parmi toutes les permutations on n'affiche que les listes possédant 3 éléments. Le programme en Prolog possède alors une seule ligne :

afficher(X):-permutation(L,[a,b,c,d,e]),append(X,[_,_],L).

Appelons le prédicat afficher dans l'interpréteur SWI-Prolog :

?- afficher(X).

Et voici les solutions affichées (en appuyant sur ; pour passer d'une ligne à l'autre) :

X = [a, b, c] ;
X = [a, b, c] ;
X = [a, b, d] ;
X = [a, b, e] ;
X = [a, b, d] ;
X = [a, b, e] ;
X = [a, c, b] ;
X = [a, c, b] ;
X = [a, d, b] ;
X = [a, e, b] ;
X = [a, d, b] ;
X = [a, e, b] ;
X = [a, c, d] ;
X = [a, c, e] ;
X = [a, d, c] ;
X = [a, e, c] ;
X = [a, d, e] ;
X = [a, e, d] ;
X = [a, c, d] ;
X = [a, c, e] ;
X = [a, d, c] ;
X = [a, e, c] ;
X = [a, d, e] ;
X = [a, e, d] ;
X = [b, a, c] ;
X = [b, a, c] ;
X = [b, a, d] ;
X = [b, a, e] ;
X = [b, a, d] ;
X = [b, a, e] ;
X = [c, a, b] ;
X = [c, a, b] ;
X = [d, a, b] ;
X = [e, a, b] ;
X = [d, a, b] ;
X = [e, a, b] ;
X = [c, a, d] ;
X = [c, a, e] ;
X = [d, a, c] ;
X = [e, a, c] ;
X = [d, a, e] ;
X = [e, a, d] ;
X = [c, a, d] ;
X = [c, a, e] ;
X = [d, a, c] ;
X = [e, a, c] ;
X = [d, a, e] ;
X = [e, a, d] ;
X = [b, c, a] ;
X = [b, c, a] ;
X = [b, d, a] ;
X = [b, e, a] ;
X = [b, d, a] ;
X = [b, e, a] ;
X = [c, b, a] ;
X = [c, b, a] ;
X = [d, b, a] ;
X = [e, b, a] ;
X = [c, d, a] ;
X = [c, e, a] ;
X = [d, c, a] ;
X = [e, c, a] ;
X = [d, e, a] ;
X = [e, d, a] ;
X = [c, d, a] ;
X = [c, e, a] ;
X = [d, c, a] ;
X = [e, c, a] ;
X = [d, e, a] ;
X = [e, d, a] ;
X = [b, c, d] ;
X = [b, c, e] ;
X = [b, d, c] ;
X = [b, e, c] ;
X = [b, d, e] ;
X = [b, e, d] ;
X = [c, b, d] ;
X = [c, b, e] ;
X = [d, b, c] ;
X = [e, b, c] ;
X = [d, b, e] ;
X = [e, b, d] ;
X = [c, d, b] ;
X = [c, e, b] ;
X = [d, c, b] ;
X = [e, c, b] ;
X = [d, e, b] ;
X = [e, d, b] ;
X = [c, d, e] ;
X = [c, e, d] ;
X = [d, c, e] ;
X = [e, c, d] ;
X = [d, e, c] ;
X = [e, d, c] ;
X = [b, c, d] ;
X = [b, c, e] ;
X = [b, d, c] ;
X = [b, e, c] ;
X = [b, d, e] ;
X = [b, e, d] ;
X = [c, b, d] ;
X = [c, b, e] ;
X = [d, b, c] ;
X = [e, b, c] ;
X = [d, b, e] ;
X = [e, b, d] ;
X = [c, d, b] ;
X = [c, e, b] ;
X = [d, c, b] ;
X = [e, c, b] ;
X = [d, e, b] ;
X = [e, d, b] ;
X = [c, d, e] ;
X = [c, e, d] ;
X = [d, c, e] ;
X = [e, c, d] ;
X = [d, e, c] ;
X = [e, d, c] ;

etc.

Le problème est qu'en prenant seulement les 3 premiers éléments des listes issues de toutes les permutations possibles de la liste d'origine on obtient inévitablement des doublons (plusieurs fois la même liste), ainsi que des permutations de chacune des listes à 3 éléments, c'est-à-dire exactement ce que l'on voulait éviter ...

Voici une autre solution, qui donne moins de réponses mais qui génère tout de même encore des doublons :

partie([X|E],P,[X|L]):-K is P-1,partie(E,K,L).
partie(E,P,[_|L]):-partie(E,P,L).
partie([],0,_).

Appelons le prédicat partie dans l'interpréteur SWI-Prolog :

?- partie(X,3,[a,b,c,d,e]).

La réponse est :

X = [a, b, c] ;
X = [a, b, c] ;
X = [a, b, c] ;
X = [a, b, d] ;
X = [a, b, d] ;
X = [a, b, e] ;
X = [a, c, d] ;
X = [a, c, d] ;
X = [a, c, e] ;
X = [a, d, e] ;
X = [b, c, d] ;
X = [b, c, d] ;
X = [b, c, e] ;
X = [b, d, e] ;
X = [c, d, e] ;

Remarque : l'emploi de la coupure dans le programme précédent devrait permettre de supprimer les doublons.

Et voici la bonne solution :

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des combinaisons d'une sous-liste en Prolog %
% Réalisé par Jean-Christophe MICHEL                     %
% Mars 2014                                              %
% www.gecif.net                                          %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

scinder(L, [], L).
scinder([T|Q], [T|L1], L2) :-
      scinder(Q, L1, L2).

solution(0,L,[], L).
solution(N,L,[T|L3],R) :-
      N>0,
      scinder(L, L1, [T|L2]),
      N1 is N-1,
      solution(N1,L2,L3,L4),
      append(L1,L4,R).

Appelons le prédicat solution dans l'interpétuer SWI-Prolog en lui passant en paramètre le nombre d'éléments voulu ainsi que la liste d'origine :

?- solution(3,[a,b,c,d,e],X,Y).

Et voici le résultat :

X = [a, b, c],
Y = [d, e] ;
X = [a, b, d],
Y = [c, e] ;
X = [a, b, e],
Y = [c, d] ;
X = [a, c, d],
Y = [b, e] ;
X = [a, c, e],
Y = [b, d] ;
X = [a, d, e],
Y = [b, c] ;
X = [b, c, d],
Y = [a, e] ;
X = [b, c, e],
Y = [a, d] ;
X = [b, d, e],
Y = [a, c] ;
X = [c, d, e],
Y = [a, b] ;

X est une liste à 3 éléments, Y est le reste de la liste (éléments de la liste d'origine n'appartenant pas à la liste X).

Si on veut seulement les listes à 3 éléments on ne spécifira pas de variable pour le dernier paramètre du prédicat solution :

?- solution(3,[a,b,c,d,e],X,_).

Et cette fois on obtient bien les 10 listes à 3 éléments pris dans la liste d'origine à 5 éléments, sans doublons de liste :

X = [a, b, c] ;
X = [a, b, d] ;
X = [a, b, e] ;
X = [a, c, d] ;
X = [a, c, e] ;
X = [a, d, e] ;
X = [b, c, d] ;
X = [b, c, e] ;
X = [b, d, e] ;
X = [c, d, e] ;

Application immédiate : la génération automatique de QCM contenant 1 bonne réponse et 3 mauvaises avec permutation des mauvaises réponses. Imaginons qu'on dispose de 10 questions sur les unités de mesure dont la réponse est unique : la bonne réponse à une question est considérée fausse pour les 9 autres. On désire obtenir tous les groupes de 4 réponses prises parmi les 10 et sans doublons quelque soit l'ordre. Le programme précédent en Prolog nous donne les 210 solutions possibles :

?- solution(4, [volt, ampère, coulomb, henry, weber, ohm, siemens, watt, joule, farad], X,_).
X = [volt, ampère, coulomb, henry] ;
X = [volt, ampère, coulomb, weber] ;
X = [volt, ampère, coulomb, ohm] ;
X = [volt, ampère, coulomb, siemens] ;
X = [volt, ampère, coulomb, watt] ;
X = [volt, ampère, coulomb, joule] ;
X = [volt, ampère, coulomb, farad] ;
X = [volt, ampère, henry, weber] ;
X = [volt, ampère, henry, ohm] ;
X = [volt, ampère, henry, siemens] ;
X = [volt, ampère, henry, watt] ;
X = [volt, ampère, henry, joule] ;
X = [volt, ampère, henry, farad] ;
X = [volt, ampère, weber, ohm] ;
X = [volt, ampère, weber, siemens] ;
X = [volt, ampère, weber, watt] ;
X = [volt, ampère, weber, joule] ;
X = [volt, ampère, weber, farad] ;
X = [volt, ampère, ohm, siemens] ;
X = [volt, ampère, ohm, watt] ;
X = [volt, ampère, ohm, joule] ;
X = [volt, ampère, ohm, farad] ;
X = [volt, ampère, siemens, watt] ;
X = [volt, ampère, siemens, joule] ;
X = [volt, ampère, siemens, farad] ;
X = [volt, ampère, watt, joule] ;
X = [volt, ampère, watt, farad] ;
X = [volt, ampère, joule, farad] ;
X = [volt, coulomb, henry, weber] ;
X = [volt, coulomb, henry, ohm] ;
X = [volt, coulomb, henry, siemens] ;
X = [volt, coulomb, henry, watt] ;
X = [volt, coulomb, henry, joule] ;
X = [volt, coulomb, henry, farad] ;
X = [volt, coulomb, weber, ohm] ;
X = [volt, coulomb, weber, siemens] ;
X = [volt, coulomb, weber, watt] ;
X = [volt, coulomb, weber, joule] ;
X = [volt, coulomb, weber, farad] ;
X = [volt, coulomb, ohm, siemens] ;
X = [volt, coulomb, ohm, watt] ;
X = [volt, coulomb, ohm, joule] ;
X = [volt, coulomb, ohm, farad] ;
X = [volt, coulomb, siemens, watt] ;
X = [volt, coulomb, siemens, joule] ;
X = [volt, coulomb, siemens, farad] ;
X = [volt, coulomb, watt, joule] ;
X = [volt, coulomb, watt, farad] ;
X = [volt, coulomb, joule, farad] ;
X = [volt, henry, weber, ohm] ;
X = [volt, henry, weber, siemens] ;
X = [volt, henry, weber, watt] ;
X = [volt, henry, weber, joule] ;
X = [volt, henry, weber, farad] ;
X = [volt, henry, ohm, siemens] ;
X = [volt, henry, ohm, watt] ;
X = [volt, henry, ohm, joule] ;
X = [volt, henry, ohm, farad] ;
X = [volt, henry, siemens, watt] ;
X = [volt, henry, siemens, joule] ;
X = [volt, henry, siemens, farad] ;
X = [volt, henry, watt, joule] ;
X = [volt, henry, watt, farad] ;
X = [volt, henry, joule, farad] ;
X = [volt, weber, ohm, siemens] ;
X = [volt, weber, ohm, watt] ;
X = [volt, weber, ohm, joule] ;
X = [volt, weber, ohm, farad] ;
X = [volt, weber, siemens, watt] ;
X = [volt, weber, siemens, joule] ;
X = [volt, weber, siemens, farad] ;
X = [volt, weber, watt, joule] ;
X = [volt, weber, watt, farad] ;
X = [volt, weber, joule, farad] ;
X = [volt, ohm, siemens, watt] ;
X = [volt, ohm, siemens, joule] ;
X = [volt, ohm, siemens, farad] ;
X = [volt, ohm, watt, joule] ;
X = [volt, ohm, watt, farad] ;
X = [volt, ohm, joule, farad] ;
X = [volt, siemens, watt, joule] ;
X = [volt, siemens, watt, farad] ;
X = [volt, siemens, joule, farad] ;
X = [volt, watt, joule, farad] ;
X = [ampère, coulomb, henry, weber] ;
X = [ampère, coulomb, henry, ohm] ;
X = [ampère, coulomb, henry, siemens] ;
X = [ampère, coulomb, henry, watt] ;
X = [ampère, coulomb, henry, joule] ;
X = [ampère, coulomb, henry, farad] ;
X = [ampère, coulomb, weber, ohm] ;
X = [ampère, coulomb, weber, siemens] ;
X = [ampère, coulomb, weber, watt] ;
X = [ampère, coulomb, weber, joule] ;
X = [ampère, coulomb, weber, farad] ;
X = [ampère, coulomb, ohm, siemens] ;
X = [ampère, coulomb, ohm, watt] ;
X = [ampère, coulomb, ohm, joule] ;
X = [ampère, coulomb, ohm, farad] ;
X = [ampère, coulomb, siemens, watt] ;
X = [ampère, coulomb, siemens, joule] ;
X = [ampère, coulomb, siemens, farad] ;
X = [ampère, coulomb, watt, joule] ;
X = [ampère, coulomb, watt, farad] ;
X = [ampère, coulomb, joule, farad] ;
X = [ampère, henry, weber, ohm] ;
X = [ampère, henry, weber, siemens] ;
X = [ampère, henry, weber, watt] ;
X = [ampère, henry, weber, joule] ;
X = [ampère, henry, weber, farad] ;
X = [ampère, henry, ohm, siemens] ;
X = [ampère, henry, ohm, watt] ;
X = [ampère, henry, ohm, joule] ;
X = [ampère, henry, ohm, farad] ;
X = [ampère, henry, siemens, watt] ;
X = [ampère, henry, siemens, joule] ;
X = [ampère, henry, siemens, farad] ;
X = [ampère, henry, watt, joule] ;
X = [ampère, henry, watt, farad] ;
X = [ampère, henry, joule, farad] ;
X = [ampère, weber, ohm, siemens] ;
X = [ampère, weber, ohm, watt] ;
X = [ampère, weber, ohm, joule] ;
X = [ampère, weber, ohm, farad] ;
X = [ampère, weber, siemens, watt] ;
X = [ampère, weber, siemens, joule] ;
X = [ampère, weber, siemens, farad] ;
X = [ampère, weber, watt, joule] ;
X = [ampère, weber, watt, farad] ;
X = [ampère, weber, joule, farad] ;
X = [ampère, ohm, siemens, watt] ;
X = [ampère, ohm, siemens, joule] ;
X = [ampère, ohm, siemens, farad] ;
X = [ampère, ohm, watt, joule] ;
X = [ampère, ohm, watt, farad] ;
X = [ampère, ohm, joule, farad] ;
X = [ampère, siemens, watt, joule] ;
X = [ampère, siemens, watt, farad] ;
X = [ampère, siemens, joule, farad] ;
X = [ampère, watt, joule, farad] ;
X = [coulomb, henry, weber, ohm] ;
X = [coulomb, henry, weber, siemens] ;
X = [coulomb, henry, weber, watt] ;
X = [coulomb, henry, weber, joule] ;
X = [coulomb, henry, weber, farad] ;
X = [coulomb, henry, ohm, siemens] ;
X = [coulomb, henry, ohm, watt] ;
X = [coulomb, henry, ohm, joule] ;
X = [coulomb, henry, ohm, farad] ;
X = [coulomb, henry, siemens, watt] ;
X = [coulomb, henry, siemens, joule] ;
X = [coulomb, henry, siemens, farad] ;
X = [coulomb, henry, watt, joule] ;
X = [coulomb, henry, watt, farad] ;
X = [coulomb, henry, joule, farad] ;
X = [coulomb, weber, ohm, siemens] ;
X = [coulomb, weber, ohm, watt] ;
X = [coulomb, weber, ohm, joule] ;
X = [coulomb, weber, ohm, farad] ;
X = [coulomb, weber, siemens, watt] ;
X = [coulomb, weber, siemens, joule] ;
X = [coulomb, weber, siemens, farad] ;
X = [coulomb, weber, watt, joule] ;
X = [coulomb, weber, watt, farad] ;
X = [coulomb, weber, joule, farad] ;
X = [coulomb, ohm, siemens, watt] ;
X = [coulomb, ohm, siemens, joule] ;
X = [coulomb, ohm, siemens, farad] ;
X = [coulomb, ohm, watt, joule] ;
X = [coulomb, ohm, watt, farad] ;
X = [coulomb, ohm, joule, farad] ;
X = [coulomb, siemens, watt, joule] ;
X = [coulomb, siemens, watt, farad] ;
X = [coulomb, siemens, joule, farad] ;
X = [coulomb, watt, joule, farad] ;
X = [henry, weber, ohm, siemens] ;
X = [henry, weber, ohm, watt] ;
X = [henry, weber, ohm, joule] ;
X = [henry, weber, ohm, farad] ;
X = [henry, weber, siemens, watt] ;
X = [henry, weber, siemens, joule] ;
X = [henry, weber, siemens, farad] ;
X = [henry, weber, watt, joule] ;
X = [henry, weber, watt, farad] ;
X = [henry, weber, joule, farad] ;
X = [henry, ohm, siemens, watt] ;
X = [henry, ohm, siemens, joule] ;
X = [henry, ohm, siemens, farad] ;
X = [henry, ohm, watt, joule] ;
X = [henry, ohm, watt, farad] ;
X = [henry, ohm, joule, farad] ;
X = [henry, siemens, watt, joule] ;
X = [henry, siemens, watt, farad] ;
X = [henry, siemens, joule, farad] ;
X = [henry, watt, joule, farad] ;
X = [weber, ohm, siemens, watt] ;
X = [weber, ohm, siemens, joule] ;
X = [weber, ohm, siemens, farad] ;
X = [weber, ohm, watt, joule] ;
X = [weber, ohm, watt, farad] ;
X = [weber, ohm, joule, farad] ;
X = [weber, siemens, watt, joule] ;
X = [weber, siemens, watt, farad] ;
X = [weber, siemens, joule, farad] ;
X = [weber, watt, joule, farad] ;
X = [ohm, siemens, watt, joule] ;
X = [ohm, siemens, watt, farad] ;
X = [ohm, siemens, joule, farad] ;
X = [ohm, watt, joule, farad] ;
X = [siemens, watt, joule, farad] ;

En traitant ce fichier texte par expressions régulières on convertit chaque ligne en question, avec le premier champ comme bonne réponse et les 3 autres comme mauvaises réponses, et sans la réponse "Aucune de ces propositions". Ceci n'est qu'un exemple montrant comment obtenir 210 questions de QCM instantanément grâce à Prolog.

Autre application, cette fois pour générer des QCM avec des cases à cocher : on dispose de 8 affirmations vraies et 8 affirmations fausses. Les 8 affirmations vraies sont notées v1 à v8, et les 8 affirmations fausses sont notées f1 à f8. On désire obtenir tous les ensembles de 4 affirmations prises parmi les 16, et sans répétitions des groupes.

Appelons encore le prédicat solution :

?- solution(4, [v1,v2,v3,v4,v5,v6,v7,v8,f1,f2,f3,f4,f5,f6,f7,f8], X,_).

Il nous donne tous les groupes (plusieurs centaines ...) de 4 affirmations parmi les 16 et sans doublons :

X = [v2, v5, f3, f5] ;
X = [v2, v5, f3, f6] ;
X = [v2, v5, f3, f7] ;
X = [v2, v5, f3, f8] ;
X = [v2, v5, f4, f5] ;
X = [v2, v5, f4, f6] ;
X = [v2, v5, f4, f7] ;
X = [v2, v5, f4, f8] ;
X = [v2, v5, f5, f6] ;
X = [v2, v5, f5, f7] ;
X = [v2, v5, f5, f8] ;
X = [v2, v5, f6, f7] ;
X = [v2, v5, f6, f8] ;
X = [v2, v5, f7, f8] ;
X = [v2, v6, v7, v8] ;
X = [v2, v6, v7, f1] ;
X = [v2, v6, v7, f2] ;
X = [v2, v6, v7, f3] ;
X = [v2, v6, v7, f4] ;
X = [v2, v6, v7, f5] ;
X = [v2, v6, v7, f6] ;
X = [v2, v6, v7, f7] ;
X = [v2, v6, v7, f8] ;
X = [v2, v6, v8, f1] ;
X = [v2, v6, v8, f2] ;
X = [v2, v6, v8, f3] ;
X = [v2, v6, v8, f4] ;
X = [v2, v6, v8, f5] ;
X = [v2, v6, v8, f6] ;
X = [v2, v6, v8, f7] ;
X = [v2, v6, v8, f8] ;
X = [v2, v6, f1, f2] ;
X = [v2, v6, f1, f3] ;
X = [v2, v6, f1, f4] ;
X = [v2, v6, f1, f5] ;
X = [v2, v6, f1, f6] ;
X = [v2, v6, f1, f7] ;
X = [v2, v6, f1, f8] ;
X = [v2, v6, f2, f3] ;
X = [v2, v6, f2, f4] ;
X = [v2, v6, f2, f5] ;
X = [v2, v6, f2, f6] ;

etc.

Mais s'agissant de cases à cocher, il reste à retrouver toutes les questions ne possédant que des affirmations fausses afin d'y rajouter la case à cocher [x] Aucune de ces propositions. Et ce n'est pas en modifiant le programme en Prolog que nous allons détecter ces questions particulières, mais tout simplement avec l'expression régulière suivante qui détecte toutes les lignes possédant 4 réponses fausses (4 fois fn sur la même ligne, où n est un nombre) :

((.*f\d{1}){4}.*)

Le groupe $1 représentant toute la ligne, il suffit de la remplacer par exemple par $1 : TOUT FAUX dans Dreamweaver pour "marquer" la ligne correspondante.

Ensuite, toujours en utilisant les expressions régulières, chaque affirmation est remplacée par son intitulé, pour les lignes marquées on ajoute la case à cocher [x] Aucune de ces propositions, et pour toutes les lignes non marquées on ajoute la case à cocher [ ] Aucune de ces propositions. On obtient ainsi, grâce à Prolog et aux expressions régulières, plusieurs centaines de questions de type cases à cocher où la question est de la forme "Cochez toutes les affirmations vraies parmi les 4 suivantes".

Voici une autre solution pour obtenir toutes les listes à P éléments à partir d'une liste de N éléments et sans répétitions. Cette solution simple définit un seul prédicat liste et n'utilise pas le prédicat append de SWI-Prolog :

liste(0,_,[]).
liste(N,[X|T],[X|L]):-N>0,N1 is N-1,liste(N1,T,L).
liste(N,[_|T],L):-N>0,liste(N,T,L).

Et voici le résultat dans SWI-Prolog :

?- liste(3,[a,b,c,d,e],X).
X = [a, b, c] ;
X = [a, b, d] ;
X = [a, b, e] ;
X = [a, c, d] ;
X = [a, c, e] ;
X = [a, d, e] ;
X = [b, c, d] ;
X = [b, c, e] ;
X = [b, d, e] ;
X = [c, d, e] ;

Mais le nombre de combinaisons obtenues peut vite devenir très important. Voici un programme en Prolog qui donne le nombre de combinaisons de P éléments pris dans un ensemble de N éléments :

comb(_,0,1).
comb(N,P,R):-N>0,M is N-1,Q is P-1,comb(M,Q,S),R is N*S/P.

Combien existe-t-il de liste à 3 éléments pris dans une liste à 5 éléments ?

?- comb(5,3,X).
X = 10 .

Réponse : 10 listes. Il s'agit des 10 listes ci-dessus obtenues en appelant liste(3,[a,b,c,d,e],X).

Et si maintenant on appelle liste(4,[v1,v2,v3,v4,v5,v6,v7,v8,f1,f2,f3,f4,f5,f6,f7,f8],X). combien de listes à 4 éléments obtient-on à partir de la liste à 16 éléments ? Demandons à Prolog :

?- comb(16,4,X).
X = 1820 .

Réponse : 1820 listes. Et on arrive à un nouveau problème : comment récupérer ces 1820 listes dans un fichier texte sans appuyer 1820 fois sur le touche point-virgule du clavier ? La solution consiste à créer une liste contenant toutes les solutions puis à afficher cette liste. Pour créer une liste contenant toutes les solutions fournies par un prédicat il existe le prédicat prédéfini findall. Par exemple en appelant findall(X,liste(3,[a,b,c,d,e],X),L) on obtient une liste L contenant toutes les valeurs de X issues du prédicat liste :

Il reste à afficher la liste L avec 1 élément par ligne. Pour cela on ré-utilise le prédicat afficher_liste donné plus haut :

afficher_liste([X|L]) :- writeln(X), afficher_liste(L).

Et dans SWI-Prolog on lance la ligne de commande suivante :

?- findall(X,liste(3,[a,b,c,d,e],X),L),afficher_liste(L).

Ce qui nous donne d'un coup l'ensemble des solutions avec une liste par ligne sans afficher X = et sans devoir appuyer sur la touche point-virgule pour faire défiler les solutions :

[a,b,c]
[a,b,d]
[a,b,e]
[a,c,d]
[a,c,e]
[a,d,e]
[b,c,d]
[b,c,e]
[b,d,e]
[c,d,e]

Et de la même manière ?- findall(X,liste(4,[v1,v2,v3,v4,v5,v6,v7,v8,f1,f2,f3,f4,f5,f6,f7,f8],X),L),afficher_liste(L). nous donne instantanément les 1820 listes attendues.

Enfin, pour récupérer le résultat dans un fichier texte il suffit de rediriger la sortie standard. Pour cela :

On prépare le fichier liste.pl suivant contenant le programme en Prolog (il se résume aux 2 prédicats liste et afficher_liste) :

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Génération des combinaisons d'une sous-liste en Prolog %
% Réalisé par Jean-Christophe MICHEL                     %
% Mars 2014                                              %
% www.gecif.net                                          %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

afficher_liste([X|L]) :- writeln(X), afficher_liste(L).

liste(0,_,[]).
liste(N,[X|T],[X|L]):-N>0,N1 is N-1,liste(N1,T,L).
liste(N,[_|T],L):-N>0,liste(N,T,L).

On prépare le fichier entree.txt suivant contenant les commandes à taper dans l'interpréteur :

findall(X,liste(8,[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p],X),L),afficher_liste(L).
halt.

Puis on lance la commande suivante sur la ligne de commande de Windows XP en redirigeant l'entrée et la sortie standard :

swipl liste.pl < entree.txt > sortie.txt

On obtient alors instantanément dans le fichier sortie.txt l'ensemble des listes demandées (12870 listes dans l'exemple ci-dessus : ensemble de 8 éléments pris dans un ensemble de 16 éléments). Même en cas de plusieurs milliers de listes générées, le résultat arrive instantanément dans le fichier sortie.txt (ce qui n'est pas le cas dans la fenêtre graphique de SWI-Prolog).

Afin de diversifier les combinaisons des listes générées, voici un autre programme qui attend en paramètre une liste de liste, et qui renvoie en sortie toutes les combinaisons de listes qu'il est possible de faire en prenant 1 élément dans chacune des listes de départ :

% Retourne les combinaisons une par une
combi([L|Q], [Elem|R]) :- member(Elem, L),combi(Q, R).
combi([], []).

% Retourne la liste de toutes les combinaisons
combinaisons(Listes, Combis) :- findall(C, combi(Listes, C), Combis).

Exemple : en partant de 3 listes on génère toutes les listes possibles à 3 éléments en prenant 1 élément dans chaque liste :

?- combinaisons([[a,b], [c,d,e], [f]], L).

L = [[a, c, f], [a, d, f], [a, e, f], [b, c, f], [b, d, f], [b, e, f]]

Autre exemple : en partant de 4 listes on génère toutes les listes possibles à 4 éléments :

?- combinaisons([[a,b], [c,d,e], [f,g,h], [i,j]], L),afficher_liste(L).

On obtient les 36 listes à 4 éléments suivantes :

[a,c,f,i]
[a,c,f,j]
[a,c,g,i]
[a,c,g,j]
[a,c,h,i]
[a,c,h,j]
[a,d,f,i]
[a,d,f,j]
[a,d,g,i]
[a,d,g,j]
[a,d,h,i]
[a,d,h,j]
[a,e,f,i]
[a,e,f,j]
[a,e,g,i]
[a,e,g,j]
[a,e,h,i]
[a,e,h,j]
[b,c,f,i]
[b,c,f,j]
[b,c,g,i]
[b,c,g,j]
[b,c,h,i]
[b,c,h,j]
[b,d,f,i]
[b,d,f,j]
[b,d,g,i]
[b,d,g,j]
[b,d,h,i]
[b,d,h,j]
[b,e,f,i]
[b,e,f,j]
[b,e,g,i]
[b,e,g,j]
[b,e,h,i]
[b,e,h,j]


Avec SWI-Prolog il existe un grand nombre de prédicats prédéfinis et bien pratiques pour manipuler les listes, comme par exemple sort qui trie une liste en supprimant les doublons ou encore list_to_set qui convertit une liste en ensemble, c'est-à-dire encore en supprimant les doublons.

Exemples :

1 ?- sort([b,d,c,a],L).
L = [a, b, c, d].

2 ?- sort([[a,b],[c,d],[a,b]],L).
L = [[a, b], [c, d]].

3 ?- list_to_set([a,b,c,a,d,c,b],L).
L = [a, b, c, d].

flatten(L1,L2) applanit et unifie une liste composée L1. L1 peut contenir de nombreuses listes imbriquées récursivement. flatten extrait tous les éléments contenus dans L1 et stoque le résultat dans une liste "plane" L2 (à une seule dimension). Exemple :

1 ?- flatten([[1,[2],3], [[4,5],[6,7]]], L).
L = [1, 2, 3, 4, 5, 6, 7].

2 ?- flatten([[1], [2,3,4,5]], L).
L = [1, 2, 3, 4, 5].

Avec select(X,L1,L2), X prend pour valeur chaque éléments de la liste L1, et la liste L2 est égale à L1 privée de l'élément X. Exemple :

1 ?- select(X, [1,2,3,4], L).
X = 1,
L = [2, 3, 4] ;
X = 2,
L = [1, 3, 4] ;
X = 3,
L = [1, 2, 4] ;
X = 4,
L = [1, 2, 3] ;

Dans tous les cas on retiendra qu'il est facile en Prolog de générer automatiquement toute sorte de listes répondant à certains critères, en utilisant des prédicats prédéfinis ou en s'inspirant des exemples donnés ci-dessus, et ce sans forcément "penser en Prolog" ou maîtriser la totalité du langage. Enfin, plus que jamais, il est totalement inutile de ré-inventer la roue en ré-écrivant les prédicats prédéfinis dans SWI-Prolog et qui ne demande qu'à être utilisés ...

Cliquez ici pour voir d'autres exemples de génération automatique de questions pour QCM en utilisant Prolog.

Retour en haut de la page

 

La programmation logique avec contraintes

Le module clpfd de SWI-Prolog permet de programmer avec contraintes.

Un premier exemple : on recherche les nombres entiers supérieurs à 2 dans l'intervalle 1..5 :

Le code source (il charge le module clpfd puis définit les contraintes sur la variable X) :

:-use_module(library(clpfd)).
solution(L):-
L=[X],
X in 1..5,
X#>2,
labeling([],L).

Appelons le prédicat solution dans l'interpréteur Prolog :

?- solution(L).
L = [3] ;
L = [4] ;
L = [5].

Prolog nous ressort les 3 solutions du problèmes : les entiers 3, 4 et 5.

Ajoutons une nouvelle contraintes afin de limiter les solutions possibles :

:-use_module(library(clpfd)).
solution(L):-
L=[X],
X in 1..5,
X#>2,
X#=<3,
labeling([],L).

Cette fois il n'y a qu'une seule solution : X=3

?- solution(L).
L = [3].

 

Principe d'un programme logique avec contraites :

Le programme est composé d'un seul prédicat solution contenant 3 parties :

1 - la déclaration de toutes les variables du problème dans une liste L

2 - l'écriture des différentes contraintes liant toutes les variables

3 - l'appel du predicat labelling pour la recherche des solution

Application de la programmation logique avec contraintes : la résolution d'un système d'équation à 2 inconnues.

On cherche 2 entiers X et Y tels que 2X+4Y=20 et 7X+8Y=52. Les 2 variables à rechercher sont X et Y.

:-use_module(library(clpfd)).
solution(L):-
        % liste des variables du problèmes
        L=[X,Y],
        % intervalle arbitraire sur une variable
        
X in -100..100,
        % écriture des contraintes : il s'agit des 2 équations du système
        
2*X+4*Y#=20,
        7*X+8*Y#=52,
        % appel de labeling
        
labeling([],L).

Et en appelant le prédicat solution Prolog nous donne instantanément les deux solutions du système : X=4 et Y=3

?- solution(L).
L = [4, 3].

Autre application : recherche d'un carré magique

On cherche à placer les entiers de 1 à 9 dans un carré 3x3 de telle sorte que la somme des nombre de chaque ligne, chaque colonne et chaque diagonale soit égale à 15. Les 9 variables à trouver sont nomées X1 à X9 et représentent les 9 cases du carré magique :

X1
X2
X3
X4
X5
X6
X7
X8
X9

Le programme source :

:-use_module(library(clpfd)).
solution(L):-
        L=[X1,X2,X3,X4,X5,X6,X7,X8,X9],
        L ins 1..9,
        all_different(L),
        X1+X2+X3#=15,
        X4+X5+X6#=15,
        X7+X8+X9#=15,
        X1+X4+X7#=15,
        X2+X5+X8#=15,
        X3+X6+X9#=15,
        X3+X5+X7#=15,
        X1+X5+X9#=15,
        labeling([],L).

Prolog sort instantanément 8 solutions correspondant à un même carré magique avec différentes orientations (rotation et symétrie) :

?- solution(L).
L = [2, 7, 6, 9, 5, 1, 4, 3, 8] ;
L = [2, 9, 4, 7, 5, 3, 6, 1, 8] ;
L = [4, 3, 8, 9, 5, 1, 2, 7, 6] ;
L = [4, 9, 2, 3, 5, 7, 8, 1, 6] ;
L = [6, 1, 8, 7, 5, 3, 2, 9, 4] ;
L = [6, 7, 2, 1, 5, 9, 8, 3, 4] ;
L = [8, 1, 6, 3, 5, 7, 4, 9, 2] ;
L = [8, 3, 4, 1, 5, 9, 6, 7, 2] ;

Remarque : in impose qu'une variable appartienne à un intervalle et ins impose que toutes les variables d'une liste appartiennent à un intervalle.

all_different(L) impose que toutes les valeurs de la liste L soient différentes.

Et voici le retour ... des grilles de routement de TP :

On cherche la grille de roulement pour 12 élèves :

X1 X2 X3
X4 X5 X6
X7 X8 X9
X10 X11 X12
X13 X14 X15
X16 X17 X18
X19 X20 X21
X22 X23 X24
X25 X26 X27
X28 X29 X30
X31 X32 X33
X34 X35 X36
X37 X38 X39
X40 X41 X42
X43 X44 X45
X46 X47 X48

Voici un exemple de problème qui doit sans doute se résoudre facilement grâce à la programmation avec contraintes, mais la solution simple en Prolog reste à trouver ...

 

 

 

Retour en haut de la page

Conclusion

Cette page vous a donné tous les éléments de base pour pouvoir commencer à programmer en Prolog. Pour aller plus loin on pourra commencer par aller voir tous les prédicats prédéfinis de SWI-Prolog, notamment pour la manipulation des listes, puis ensuite découvrir des exemples où la coupure est indispensable.