Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.
Listes et coupe choix – entrainement
Les activités d’entrainement consistent à traiter des exercices d’entraînement. Vous devez d’abord tenter de traiter ces exercices sans dévoiler d’indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de découverte ou d’entraînement précédemment traités. Si vous avez besoin d’indices ou si vos solutions sont erronées, analysez les causes de vos erreurs – au besoin, demandez des explications à une personne qualifiée – et refaites les exercices concernés après un délai d’au moins une journée et au plus quelques jours.
Activité d’entraînement C.ent
C.ent1
Vous devez définir un prédicat sum permettant de produire toutes les valeurs pouvant être obtenues en additionnant des nombres donnés dans une liste d’entrée.
Par exemple, l’évaluation du but…
sum([1,10,100],S).
…doit avoir pour résultat :
S = 111
S = 11
S = 101
S = 1
S = 110
S = 10
S = 100
S = 0
On considère que la valeur 0 est correcte. Elle représente le cas où aucune des valeurs de la liste d’entrée n’est utilisée.
On peut considérer trois possibilités, dont chacune sera décrite par une clause.
- La liste d’entrée est vide. Dans ce cas, la seule valeur calculable est 0.
- La liste d’entrée n’est pas vide. Elle se décompose en
[T|R]. On s’intéresse aux sommes réalisables en utilisant la première valeur. - La liste d’entrée n’est pas vide. Elle se décompose en
[_|R]. On s’intéresse aux sommes réalisables sans utiliser la première valeur.
sum([],0). % clause 1
sum([T|R],S) :- .................... . % clause 2
sum([_|R],S) :- .................... . % clause 3
La clause 2 dit que S est réalisable en ajoutant T et une somme de valeurs de R.
La clause 3 dit que S est une somme de valeurs de R.
sum([],0).
sum([T|R],S) :- sum(R,S1), S is S1+T.
sum([_|R],S) :- sum(R,S).
C.ent2
Nous avons vu dans la partie découverte sur les listes la définition d’un prédicat pref qui permet d’obtenir tous les préfixes non vide d’une liste.
pref([T],[T|_]).
pref([T|P],[T|R]) :- pref(P,R).
Par exemple, le but…
pref(P,[1,2,3]).
…produit le résultat :
P = [1]
P = [1, 2]
P = [1, 2, 3]
On appelle sous-liste d’une liste $L$ toute suite non vide de valeurs consécutives apparaissant dans $L$. Par exemple, les sous-listes de [1,2,3] sont :
[1] [1, 2] [1, 2, 3] [2] [2, 3] [3]
Vous devez définir un prédicat sl tel que sl(S,L) spécifie que S est une sous-liste de L. Ce prédicat doit permettre de produire toutes les sous-listes d’une liste ou de déterminer si une liste est sous-liste d’une autre. Vous pouvez raisonner de manière constructive sur le premier cas d’utilisation ou de manière plus déclarative sur le deuxième.
Par exemple, le but…
sl(P,[1,2,3]).
…devra produire le résultat :
S = [1]
S = [1, 2]
S = [1, 2, 3]
S = [2]
S = [2, 3]
S = [3]
Vous pouvez vous appuyer sur cette propriété :
Soit une liste non vide
Layant pour têteTet pour resteR. Toute sous-liste deLest soit un préfixe deL, soit une sous-liste deR.
sl(S,L) :- ............... . %clause 1
sl(S,[_|R]) :- ............... . %clause 2
La clause 1 dit que tout préfixe d’une liste L est une sous-liste de L.
La clause 2 dit que toute sous liste d’une liste R est une sous liste de toute liste de la forme [_|R].
sl(S,L) :- pref(S,L).
sl(S,[_|R]) :- sl(S,R).
C.ent3
Vous devez définir un prédicat dec permettant de décomposer une liste en un de ses éléments et un reliquat qui est la liste de tous les autres éléments.
Plus précisément, dec(L,E,R) dit que E est un élément de L et que le reliquat R est la liste des autres éléments de L (dans l’ordre où ils apparaissant dans L).
Par exemple, le but…
dec([1,2,3],E,A).
…doit produire le résultat :
A = [2,3], E = 1
A = [1,3], E = 2
A = [1,2], E = 3
Une première manière évidente de décomposer une liste [T|R] est de considérer son premier élément et son reste. La clause correspondante est :
dec([T|R],T,R).
Comment décrire les autres décompositions ?
dec([T|R],T,R).
dec([T|R],E,[T|Q]) :- .......... .
La deuxième clause dit que [T|R] peut être décomposée en un élément E et un reliquat [T|Q]. Comment exprimer la relation entre R, E et Q ?
dec([T|R],T,R).
dec([T|R],E,[T|Q]) :- dec(R,E,Q).
Voici une illustration de la deuxième clause.

On appelle anagramme d’une liste L toute les listes ayant les mêmes éléments dans un ordre quelconque.
Vous devez, en utilisant notre prédicat dec, définir un prédicat ana permettant de produire les anagrammes d’une liste. Par exemple, le but…
ana([a,b,c],A).
…devra produire le résultat :
A = [a, b, c]
A = [a, c, b]
A = [b, a, c]
A = [b, c, a]
A = [c, a, b]
A = [c, b, a]
Le seul anagramme d’une liste ayant un seul élément est la liste elle-même.
Tout anagramme d’une liste L plus grande est constitué d’un élément de L suivi d’un anagramme du reliquat de la décomposition de cette liste telle que définie par le prédicat dec.
ana([E],[E]).
ana(L,[T|Q]) :- ............... .
La deuxième clause dit qu’un anagramme [T|Q] de L est constitué d’un élément T issu de la décomposition de L par dec et d’un anagramme Q du reliquat de cette décomposition.
ana([E],[E]).
ana(L,[T|Q]) :- dec(L,T,A), ana(A,Q).
On peut utiliser le prédicat ana pour produire les anagramme d’une chaîne de caractères. Pour ce faire, on dispose d’un prédicat string_chars qui établit une relation entre une chaine et une liste de caractères. Voici deux buts utilisant ce prédicat et leur résultats :
string_chars("Tim",L). --> L = ['T', i, m]
string_chars(S,['T', i, m]). --> S = "Tim"
Les caractères représentant des majuscules sont entre cotes pour les différencier des variables. Ces cotes sont facultatives pour les lettres minuscules.
Définissez un prédicat anagramme permettant de produire sous forme de chaines les anagrammes d’une chaine. Par exemple, le but…
anagramme("Tomy",A).
…produit tous les anagrammes du mot "Tomy".
A = "Tomy"
A = "Toym"
A = "Tmoy"
A = "Tmyo"
A = "Tyom"
A = "Tymo"
etc. (18 autres réponses)
anagramme(S,A) :-
string_chars(S,L),
ana(L,M),
string_chars(A,M).
C.ent4
Vous devez définir un prédicat sd permettant de supprimer les doublons (valeurs ayant plusieurs occurrences) dans une liste.
Si L_in est une liste connue et S_out est une variable non instanciée, alors le but…
sd(L_in, S_out).
Fait remonter dans la variable S_out une liste contenant exactement une occurrence de chaque valeur de L_in.
Par exemple, l’évaluation de…
sd([2,1,2,3,1,1,3],F).
…produit le résultat :
F = [2, 1, 3]
Vous pouvez utiliser le prédicat standard member qui permet de vérifier si une valeur est dans une liste. Voici deux exemples de buts construits avec ce prédicat et leur résultats :
member(1,[2,1,1,3,2]). --> true
member(4,[2,1,1,3,2]). --> false
Quant la liste d’entrée et vide, la liste de sortie l’est aussi.
Si le premier élément T de la liste d’entrée est aussi dans le reste Q de cette liste, alors la liste de sortie est obtenue en supprimant les doublons de Q.
Si le premier élément T de la liste d’entrée n’est pas dans le reste Q de cette liste, alors la liste de sortie est constituée de T et de la liste obtenue en supprimant les doublons de Q.
sd([],[]).
sd([T|R],.....) :- member(T,R),!, .......... .
sd([T|R],.....) :- .......... .
La première clause concerne le cas où le premier élément T de la liste d’entrée apparait également dans le reste R de cette liste. On ne conservera pas cette première occurrence et la liste de sortie sera obtenue en supprimant les doublons de R. En raison de la présence du coupe-choix, la troisième clause ne sera prise en compte que si T n’est pas dans R.
sd([],[]).
sd([T|R],S) :- member(T,R),!, sd(R,S).
sd([T|R],[T|S]) :- sd(R,S).
Activité d’approfondissement
Vous commencez à avoir une certaine aisance avec la manipulation des listes ? Je vous propose maintenant de résoudre des problèmes avec Prolog.
C.top1
Nous allons utiliser Prolog pour résoudre le problème suivant :
Un berger est sur la rive gauche d’une rivière en présence d’un loup, d’une chèvre et d’une salade. Il peut traverser la rivière soit seul, soit avec la chèvre, soit avec la salade, soit avec le loup.
Il ne doit en aucun cas laisser la chèvre seule avec le loup ou avec la salade sur une des rives.
Il faut trouver un scénario permettant, en un nombre donné de traversées, d’emmener la chèvre, le loup, le berger et la salade sur la rive droite.

Pour résoudre un tel problème, nous devons trouver un moyen de représenter les données. Il y a de nombreuses possibilités et j’en ai choisi une, mais vous pouvez en chercher d’autres.
On appelle état une donnée représentant les positions respectives du berger, du loup, de la chèvre et de la salade. Un état sera représenté par une liste de 4 éléments pouvant prendre deux valeurs possibles : g pour rive gauche et d pour rive droite.
Par exemple :
[g,g,d,d]représente l’état dans lequel le berger et le loup sont sur la rive gauche et la chèvre et la salade sont sur la rive droite.[d,g,d,g]représente l’état dans lequel le berger est sur la rive droite, le loup sur la rive gauche, la chèvre sur la rive droite et la salade sur la rive gauche.
On définit le prédicat op qui définit la notion de rives opposées :
op(d,g).
op(g,d).
Dans un premier temps, je vous propose de définir un prédicat bad qui détermine les états interdits. Plus précisément, bad(E) soit être satisfait si et seulement si l’état E correspond à une situation dans laquelle la chèvre et le loup ou la chèvre et la salade sont sur la même rive sans le berger.
Pourquoi les états interdits et pas les états autorisés ? Parce-qu’on peut modéliser les états interdits de manière plus concise.
Une première solution consiste à définir bad en 4 faits comme ceci :
bad([g,d,d,_]). % berger à gauche, loup et chèvre à droite
bad([g,_,d,d]). % berger à gauche, chèvre et salade à droite
bad([d,g,g,_]). % berger à droite, loup et chèvre à gauche
bad([d,_,g,g]). % berger à droite, chèvre et salade à gauche
Proposez une définition plus concise en deux clauses, en utilisant le prédicat op.
bad([A,B,B,_]) :- op(A,B).
bad([A,_,B,B]) :- op(A,B).
Maintenant, vous devez définir un prédicat trav permettant de déterminer si une traversée est réalisable, c’est à dire si elle correspond à une de ces 4 possibilités :
- Le berger traverse seul.
- Le berger traverse avec le loup.
- Le berger traverse avec la chèvre.
- Le berger traverse avec la salade.
Plus précisément, trav(E1,E2,T) est satisfait si et seulement si une traversée réalisable permet de passer de l’état E1 à l’état E2, T étant ce qui change de rive avec le berger. Les valeurs possibles de T sont loup, chevre, salade et rien.
Par exemple, l’évaluation du but…
trav([g,g,g,g],S,T).
…a pour résultats :
S = [d, d, g, g], T = loup
S = [d, g, d, g], T = chevre
S = [d, g, g, d], T = salade
S = [d, g, g, g], T = rien
La première solution dit que le berger et le loup ont changé de rive, puisque le nouvel état est [d,d,g,g]. La quatrième solution dit que le berger traverse seul. Le nouvel état, [d,g,g,g] indique que le loup, le chèvre et la salade sont restés sur la rive gauche.
On peut définir trav en 4 clauses correspondant respectivement aux cas où le berger traverse seul, avec le loup, avec la chèvre et avec la salade. Voici la première clause correspondant au cas où le berger traverse seul :
trav([D,L,C,S],[A,L,C,S],rien) :- op(D,A).
Les positions L, C et S, du loup, de la chèvre et de la salade, ne changent pas de valeur entre l’état avant la traversée (premier slot) et l’état après la traversée (deuxième slot). Par contre, la position du berger (premier slot) passe de g à d ou de d à g. (La variable D représente la rive de départ et la variable A la rive d’arrivée.)
À vous trouver les trois clauses restantes.
trav([D,L,C,S],[A,L,C,S],rien) :- op(D,A).
trav([D,D,C,S],[A,A,C,S],loup) :- op(D,A).
trav([D,L,D,S],[A,L,A,S],chevre) :- op(D,A).
trav([D,L,C,D],[A,L,C,A],salade) :- op(D,A).
Il vous reste à définir le prédicat transp tel que transp(I,F,N,L) qui produise, si applicable, la liste L des traversées permettant de passer d’un état initial I à un état final F en N étapes.
Par exemple, l’évaluation du but…
transp([g,g,g,g],[d,d,d,d],7,Plan).
…doit produire les listes :
Plan = [chevre, rien, loup, chevre, salade, rien, chevre]
Plan = [chevre, rien, salade, chevre, loup, rien, chevre]
…qui sont les deux solutions du problème en 7 étapes.
La première liste s’interprète de la manière suivante :
- Le berger traverse avec la chèvre.
- Il revient seul sur la rive gauche.
- Il retourne sur la rive droite avec le loup.
- Il revient sur la rive gauche avec la chèvre.
- Il retourne sur la rive droite avec la salade.
- Il revient seul sur la rive gauche.
- Il traverse une dernière fois de gauche à droite avec la chèvre.
Si l’état initial et l’état final sont identiques, le transport nécessite 0 étapes et la liste des traversées est vide, ce qui correspond à la clause :
transp(F,F,0,[]).
Il reste à écrire la clause récursive qui permet de passer d’un état initial à un état final avec un nombre N de traversées supérieur à 0.
Voici le début de le deuxième clause :
transp(I,F,N,[E|S]) :- N>0, .............................. .
Voici une version à compléter de la deuxième clause
transp(I,F,N,[E|S]) :- N>0, trav(I,J,E), not(bad(J)),
.............................. .
Passer de l’état
Ià l’étatFen un nombreN>0d’étapes suppose :
- de faire une traversée
Epermettant de passer de l’étatIà un étatJ,- que
Jsoit un état autorisé,- …
transp(F,F,0,[]).
transp(I,F,N,[E|S]) :- N>0, trav(I,J,E), not(bad(J)),
N1 is N-1, transp(J,F,N1,S).
La solution complète est donc :
op(d,g).
op(g,d).
bad([A,B,B,_]) :- op(A,B).
bad([A,_,B,B]) :- op(A,B).
trav([D,D,C,S],[A,A,C,S],loup) :- op(D,A).
trav([D,L,D,S],[A,L,A,S],chevre) :- op(D,A).
trav([D,L,C,D],[A,L,C,A],salade) :- op(D,A).
trav([D,L,C,S],[A,L,C,S],rien) :- op(D,A).
transp(F,F,0,[]).
transp(I,F,N,[E|S]) :- N>0, trav(I,J,E), not(bad(J)),
N1 is N-1, transp(J,F,N1,S).
Ce qui est remarquable, c’est que ce programme de résolution comporte moins de caractères que l’énoncé du problème à résoudre ! Sans compter les espaces, l’énoncé comporte 402 caractères alors que le programme complet en comporte 319.
Nous avons donc là une illustration de la puissance d’expression de Prolog. Certes, le passage de l’énoncé au programme est loin d’être évident et nécessite une certaine expérience, mais une fois maîtrisée, une même approche peut être utilisée pour résoudre de nombreux problèmes.
Dans cet exercice, nous avons traité un problème de planification. Dans le suivant, nous abordons un casse-tête célèbre.
C.top2
Nous allons maintenant nous attaquer à un casse-tête très célèbre : le problème du zèbre. Voici une variante moderne de l’énoncé :
On considère cinq maisons, toutes de couleurs différentes (rouge, bleu, jaune, blanc, vert), dans lesquelles logent cinq personnes de professions différentes (peintre, sculpteur, diplomate, médecin et violoniste) et de nationalités différentes (anglaise, espagnole, japonaise, norvégienne et italienne) ayant chacun une boisson favorite (thé, jus de fruits, café, lait et vin) et un animal favori (chien, escargots, renard, cheval et zèbre).
On dispose des faits suivants :
Le norvégien habite la première maison à gauche.
On boit du lait dans la maison du milieu.
L’Anglais habite la maison rouge.
L’Espagnol possède un chien.
Le Japonais est peintre.
L’Italien boit du thé.
Le propriétaire de la maison verte boit du café.
Le sculpteur élève des escargots.
Le diplomate habite la maison jaune.
Le violoniste boit du jus de fruit.
La maison verte est a droite de la blanche.
Le Norvégien habite a cote de la maison bleue.
Le renard est dans une maison voisine de celle du médecin.
Le cheval est à coté de la maison du diplomate.
On veut savoir quelle est la couleur, la nationalité, la boisson, l’animal et la profession associés à chacune des maisons.

Il nous faut une représentation des informations à rechercher. Il existe plusieurs approches possibles, plus ou moins efficaces. Je vous propose de représenter chacune des lignes apparaissant sur la figure précédente par une liste.
La définition du prédicat permettant la résolution du problème commence ainsi :
sol(C,N,B,A,P) :-
C=[_,_,_,_,_],
N=[norvege,_,_,_,_],
B=[_,_,lait,_,_],
A=[_,_,_,_,_],
P=[_,_,_,_,_],
% À compléter
- La variable
Creprésente la liste des couleurs dans l’ordre des maisons dans le rue, en partant de la gauche. - La variable
Nreprésente la liste des nationalités dans le même ordre. - La variable
Breprésente la liste des boissons dans le même ordre. - La variable
Areprésente la liste des animaux dans le même ordre. - La variable
Preprésente la liste des professions dans le même ordre.
À ce stade, les seules informations qui sont données est que chaque liste contient 5 valeurs, que le norvégien habite la première maison (premier indice de l’énoncé) et que la personne qui boit du lait habite la maison centrale (deuxième indice de l’énoncé).
Il faut ajouter les autres indices de l’énoncé sous une forme exploitable par Prolog.
Commençons par le troisième indice de l’énoncé du problème :
L’anglais habite la maison rouge.
Cet indice concerne la liste C des couleurs et la liste N des nationalités. Il nous dit que anglais est dans la même position dans la liste des nationalités que rouge dans la liste des couleurs.
Pour le traduire en Prolog, nous allons définir un prédicat memePos tels que si L1, L2 sont des listes et E1, E2 des éléments, alors le but…
memePos(E1,L1,E2,L2).
…est satisfait si et seulement si la position de E1 dans L1 est la même que celle de E2 dans L2.
Voici deux exemples de buts et les résultats de leurs évaluations :
memePos(b,[a,b,c],c,[d,c,a]). --> true
memePos(a,[a,b,c],c,[d,c,a]). --> false
Donnez la définition de memePos.
Les deux éléments apparaissant en tête de chaque liste sont dans la même position (cas trivial).
Si deux éléments apparaissent en même position dans les restes de deux listes alors ils apparaissent en même positions dans ces deux listes (clause récursive).
memePos(E1,[E1|_],E2,[E2|_]).
memePos(E1,[_|R1],E2,[_|R2]) :- memePos(E1,R1,E2,R2).
Continuez à compléter la définition du prédicat sol en y ajoutant les indices 3 à 10 de l’énoncé.
L’indice n°3 s’exprime de cette manière :
memePos(anglais,N,rouge,C)
Le symbole
anglaisapparait en même position dans le liste des nationalité que le symbolerougedans la liste des couleurs.
sol(C,N,B,A,P) :-
C=[_,_,_,_,_],
N=[norvegien,_,_,_,_], % indice 1
B=[_,_,lait,_,_], % indice 2
A=[_,_,_,_,_],
P=[_,_,_,_,_],
memePos(anglais,N,rouge,C), % indice 3
memePos(chien,A,espagnol,N), % indice 4
memePos(japonais,N,peintre,P), % indice 5
memePos(italien,N,the,B), % indice 6
memePos(verte,C,cafe,B), % indice 7
memePos(sculpteur,P,escargots,A), % indice 8
memePos(diplomate,P,jaune,C), % indice 9
memePos(violoniste,P,jus,B), % indice 10
À ce stade, il peut être intéressant de tester la résolution du but…
sol(C,N,B,A,P).
…pour voir si Prolog peut faire des déductions à partir des indices donnés.
Il s’avère que oui. Cette évaluation produit de nombreuses réponses compatibles aves les données fournies, telle que :
A = [escargots, _1840, chien, _1852, _1858],
B = [café, jus, lait, _1942, the],
C = [verte, rouge, jaune, _1818, _1824],
N = [norvegien, anglais, espagnol, japonais, italien],
P = [sculpteur, violoniste, diplomate, peintre, _656]
Les variables commençant par le caractère _ sont non instanciées. Attention, le fait que escargots soit associé à la première maison dans cette réponse n’implique pas que ce soit le cas dans la solution du problème complet. Parmi les nombreuses solutions du problème partiel, certaines associent l’escargot à d’autres maisons.
Intéressons nous maintenant à l’indice n° 11 :
La maison verte est a droite de la blanche.
l’expression "à droite" est ici à prendre au sens strict. La maison verte immédiatement après la blanche.
Vous devez définir un prédicat apres tel que si L, est une liste et X, Y des éléments, alors le but…
apres(X,Y,L).
…est satisfait si et seulement si Y apparait immédiatement après X dans L.
Voici la première clause qui concerne le cas trivial où X et Y sont en début de liste :
apres(X,Y,[X,Y|_]).
Il reste à écrire la clause récursive.
apres(X,Y,[X,Y|_]).
apres(X,Y,[_|L]) :- apres(X,Y,L).
Donnez maintenant le but exprimant l’indice n°11, qui sera à ajouter dans la définition du prédicat sol.
apres(blanche,verte,C) % indice 11
Il nous reste 3 indices à encoder :
Le norvégien habite a cote de la maison bleue.
Le renard est dans une maison voisine de celle du médecin.
Le cheval est à coté de la maison du diplomate.
Dans les trois cas, on exprime qu’un élément X apparait dans une liste L1 à une position située immédiatement avant ou après la position d’un élément Y dans une liste L2.
Vous devez définir un prédicat contigu pour exprimer cette contrainte par le but :
contigu(X,L1,Y,L2).
Voici les deux clauses non récursives :
contigu(X,[X|_],Y,[_,Y|_]).
contigu(X,[_,X|_],Y,[Y|_]).
Il vous reste à écrire la clause récursive.
contigu(X,[X|_],Y,[_,Y|_]).
contigu(X,[_,X|_],Y,[Y|_]).
contigu(X,[_|R1],Y,[_|R2]) :- contigu(X,R1,Y,R2).
Ajoutez à la définition du prédicat sol les trois derniers indices.
sol(C,N,B,A,P) :-
C=[_,_,_,_,_],
N=[norvegien,_,_,_,_], % indice 1
B=[_,_,lait,_,_], % indice 2
A=[_,_,_,_,_],
P=[_,_,_,_,_],
memePos(anglais,N,rouge,C), % indice 3
memePos(chien,A,espagnol,N), % indice 4
memePos(japonais,N,peintre,P), % indice 5
memePos(italien,N,the,B), % indice 6
memePos(verte,C,café,B), % indice 7
memePos(sculpteur,P,escargots,A), % indice 8
memePos(diplomate,P,jaune,C), % indice 9
memePos(violoniste,P,jus,B), % indice 10
apres(blanche,verte,C), % indice 11
contigu(norvegien,N,bleu,C), % indice 12
contigu(renard,A,medecin,P), % indice 13
contigu(cheval,A,diplomate,P). % indice 14
En lançant le but…
sol(C,N,B,A,P).
…on obtient une seule réponse, mais incomplète :
A = [renard, cheval, escargots, chien, _1858],
B = [_1924, the, lait, jus, café],
C = [jaune, bleu, rouge, blanche, verte],
N = [norvegien, italien, anglais, espagnol, japonais],
P = [diplomate, medecin, sculpteur, violoniste, peintre]
La raison est qu’on à oublié de dire que quelqu’un boit du vin et qu’il y a un zèbre dans l’une des maisons. Vous pouvez vérifier que les symboles vin et zebre n’apparaissent pas dans le programme.
Il vous reste donc un dernier défit à relever : trouver un moyen simple d’ajouter l’information manquante.
Le prédicat standard member permet de spécifier qu’un élément E appartient à une liste L avec le but member(E,L).
sol(C,N,B,A,P) :-
C=[_,_,_,_,_],
N=[norvegien,_,_,_,_], % indice 1
B=[_,_,lait,_,_], % indice 2
A=[_,_,_,_,_],
P=[_,_,_,_,_],
memePos(anglais,N,rouge,C), % indice 3
memePos(chien,A,espagnol,N), % indice 4
memePos(japonais,N,peintre,P), % indice 5
memePos(italien,N,the,B), % indice 6
memePos(verte,C,café,B), % indice 7
memePos(sculpteur,P,escargots,A), % indice 8
memePos(diplomate,P,jaune,C), % indice 9
memePos(violoniste,P,jus,B), % indice 10
apres(blanche,verte,C), % indice 11
contigu(norvegien,N,bleu,C), % indice 12
contigu(renard,A,medecin,P), % indice 13
contigu(cheval,A,diplomate,P), % indice 14
member(zebre,A),
member(vin,B).
Nous obtenons enfin l’unique solution du problème :
A = [renard, cheval, escargots, chien, zebre],
B = [vin, the, lait, jus, café],
C = [jaune, bleu, rouge, blanche, verte],
N = [norvegien, italien, anglais, espagnol, japonais],
P = [diplomate, medecin, sculpteur, violoniste, peintre]
Ici encore, le programme qui résout le problème est plus court que l’énoncé du problème ! Sans compter les espaces, l’énoncé contient 1128 caractères alors que le programme en contient 559, soit presque deux fois moins. On peut évidemment réduire la taille de l’énoncé (et du programme), mais sans changer le fait que les tailles de l’énoncé et du programme de résolution ont le même ordre de grandeur.