En ce moment je m'amuse avec tous ces petits langages récursif méconnu tels que le Prolog et le LISP
Je viens de m'amuser à coder le système du Zébre de Lewis Carroll qui s'énonce en ces termes :
Citation : Lewis Carroll
LE PROBLEME DU ZEBRE
(attribue a Lewis Carroll, pasteur logicien et ecrivain anglais
auteur de nombreux "puzzles")
On considere cinq maisons, toutes de couleurs differentes (rouge,
bleu, jaune, blanc, vert), dans lesquelles logent cinq
professionnels (peintre, sculpteur, diplomate, docteur et
violoniste) de nationalite differente (anglaise, espagnole,
japonaise, norvegienne et italienne) ayant chacun une boisson
favorite (the, jus de fruits, cafe, lait et vin) et des animaux
favoris (chien, escargots, renard, cheval et zebre).
On dispose des faits suivants :
1. l'Anglais habite la maison rouge
2. l'Espagnol possede un chien
3. le Japonais est peintre
4. l'Italien boit du the
5. le Norvegien habite la premiere maison a gauche
6. le proprietaire de la maison verte boit du cafe
7. la maison verte est a droite de la blanche
8. le sculpteur eleve des escargots
9. le diplomate habite la maison jaune
10. on boit du lait dans la maison du milieu
11. le Norvegien habite a cote de la maison bleue
12. le violoniste boit du jus de fruit
13. le renard est dans une maison voisine de celle du medecin
14. le cheval est a cote de la maison du diplomate
Il s'agit de trouver le possesseur du zebre et le buveur de vin.
Vous pouvez essayer de le faire à la main et vous verrez qu'il faut un peu de temps pour trouver la solution.
Voici comment demander à Prolog de le résoudre.
% Prédicats de calculs
verif_attrib([[N|R]|_], A, N) :- member(A,R).
verif_attrib([_|R], A, N) :- verif_attrib(R,A,N).
est_a_gauche(L, A1, A2) :- verif_attrib(L, A1, N1), verif_attrib(L, A2, N2), N1 =:= N2 - 1.
est_a_droite(L, A1, A2) :- verif_attrib(L, A1, N1), verif_attrib(L, A2, N2), N1 =:= N2 + 1.
est_voisin(L, A1, A2) :- est_a_gauche(L,A1,A2).
est_voisin(L, A1, A2) :- est_a_droite(L,A1,A2).
test([[N, Nat, C, B, M, A]|_], N, Nat, C, B, M, A).
test([_|R], N, Nat, C, B, M, A) :- test(R, N, Nat, C, B, M, A).
% Table des contraintes
% Moteur de recherche
cherche(L) :-
test(L,_,anglais,rouge,_,_,_), % L'anglais habite la maison rouge
test(L,_,espagnol,_,_,_,chien), % L'espagnol possède un chien
test(L,_,japonais,_,_,peintre,_), % Le Japonais est peintre
test(L,_,italien,_,'thé',_,_), % L'italien boit du thé
test(L,1,norvegien,_,_,_,_), % Le norvégien habite la première maison
test(L,_,_,verte,'café',_,_), % Dans la maison verte on boit du café
est_a_gauche(L,blanche,verte), % La maison blanche est à gauche de la verte
test(L,_,_,_,_,sculpteur,escargots), % Le sculpteur élève des escargots
test(L,_,_,jaune,_,diplomate,_), % Le diplomate habite la maison jaune
test(L,3,_,_,lait,_,_), % On boit du lait dans la maison du milieu
est_voisin(L,norvegien,bleue), % Le norvégien habite à côté de la maison bleue
test(L,_,_,_,'jus de fruit',violoniste,_),% Le violoniste boit du jus de fruit
est_voisin(L,renard,docteur), % Le docteur est voisin du renard
est_voisin(L,cheval,diplomate), % Le cheval est voisin du diplomate
test(L,_,_,blanche,_,_,_), % Une maison peut-être blanche
test(L,_,_,bleue,_,_,_), % Une maison peut-être bleue
test(L,_,_,_,_,_,renard), % On peut posséder un renard
test(L,_,_,_,_,docteur,_), % On peut être docteur
test(L,_,_,_,_,_,cheval), % On peut posséder un cheval
test(L,_,_,_,_,diplomate,_), % On peut être diplomate
test(L,_,_,_,vin,_,_), % Qui boit du vin ?
test(L,_,_,_,_,_,zebre). % Qui possède le zébre ?
recherche :- cherche([[1|R1],[2|R2],[3|R3],[4|R4],[5|R5]]),
format("~tMaison 1 : ~w~n", [R1]),
format("~tMaison 2 : ~w~n", [R2]),
format("~tMaison 3 : ~w~n", [R3]),
format("~tMaison 4 : ~w~n", [R4]),
format("~tMaison 5 : ~w~n", [R5]).
Le résultat est assez bleuffant.
Comme c'est un de mes premiers programmes en Prolog, toutes idées d'améliorations sont les bienvenues.
Pour que les gens qui sont intéressé n'est pas à installer Prolog, voici le résultat :
Maison 1 : [norvegien, jaune, vin, diplomate, renard]
Maison 2 : [italien, bleue, thé, docteur, cheval]
Maison 3 : [anglais, rouge, lait, sculpteur, escargots]
Maison 4 : [espagnol, blanche, jus de fruit, violoniste, chien]
Maison 5 : [japonais, verte, café, peintre, zebre]
Traiter Lisp de petit langage récursif méconnu me paraît assez méprisant! Lisp est sûrement le langage qui a le plus révolutionné la pensée informatique en lui donnant un virage mathématique avec la programmation fonctionnelle, alliant à la fois la simplicité syntaxique et la puissance d'espression.
Pour Prolog, J'ai une remarque sur ton code, est_a_droite ne veut pas dire que c'est "juste à droite" comme tu l'as écrit, par exemple la maison du milieu est à droite de la maison de gauche.
J'ai fait le programme autrement, et ce qui m'ennuie c'est que j'obtiens une autre solution et, c'est peut-être du à l'heure tardive, je ne vois pas où est l'erreur dans ton code ou le mien, nos deux solutions satisfont aux conditions énoncées (à la nuance signalée avant près) :
Mon code tourne sur SWI-Prolog.
% maison(Couleur, Profession, Nationalite, Boisson, Animal).
%
% les extracteurs
couleur(C, maison(C, _, _, _, _)).
profession(P, maison(_, P, _, _, _)).
nationalite(N, maison(_, _, N, _, _)).
boisson(B, maison(_, _, _, B, _)).
animal(A, maison(_, _, _, _, A)).
% les maison sont dans une liste.
% la maison est au milieu
milieu(M, [_, _, M, _ , _]).
% la maison est a gauche
a_gauche(M, [M, _, _, _, _]).
% la maison N est à droite de M
% spécifique SWI-Prolog (je pense)
a_droite_de(M, N, L) :-
nth0(NM, L, M),
nth0(NN, L, N),
NM < NN.
% a cote de
% spécifique SWI-Prolog (je pense)
a_cote_de(M, N, L) :-
nth0(NM, L, M),
nth0(NN, L, N),
1 is abs(NM - NN).
resolution :-
Sol = [ _M1, _M2, _M3, _M4, _M5],
%1. l'Anglais habite la maison rouge
member(H1, Sol),
nationalite(anglais, H1),
couleur(rouge, H1),
%2. l'Espagnol possede un chien
member(H2, Sol),
nationalite(espagnol, H2),
animal(chien, H2),
%3. le Japonais est peintre
member(H3, Sol),
nationalite(japonais, H3),
profession(peintre, H3),
%4. l'Italien boit du the
member(H4, Sol),
nationalite(italien, H4),
boisson(the, H4),
%5. le Norvegien habite la premiere maison a gauche
member(H5, Sol),
nationalite(norvegien, H5),
a_gauche(H5, Sol),
%6. le proprietaire de la maison verte boit du cafe
member(H6, Sol),
couleur(vert, H6),
boisson(cafe, H6),
%7. la maison verte est a droite de la blanche
member(H7, Sol),
couleur(vert, H7),
member(H8, Sol),
couleur(blanc, H8),
a_droite_de(H8, H7, Sol),
%8. le sculpteur eleve des escargots
member(H9, Sol),
profession(sculpteur, H9),
animal(escargot, H9),
%9. le diplomate habite la maison jaune
member(H10, Sol),
profession(diplomate, H10),
couleur(jaune, H10),
%10. on boit du lait dans la maison du milieu
member(H11, Sol),
boisson(lait, H11),
milieu(H11, Sol),
%11. le Norvegien habite a cote de la maison bleue
member(H12, Sol),
nationalite(norvegien, H12),
member(H13, Sol),
couleur(bleu, H13),
a_cote_de(H12, H13, Sol),
%12. le violoniste boit du jus de fruit
member(H14, Sol),
boisson(jus_de_fruit, H14),
profession(violoniste, H14),
%13. le renard est dans une maison voisine de celle du medecin
member(H15, Sol),
animal(renard, H15),
member(H16, Sol),
profession(medecin, H16),
a_cote_de(H15, H16, Sol),
%14. le cheval est a cote de la maison du diplomate
member(H17, Sol),
animal(cheval, H17),
member(H18, Sol),
profession(diplomate, H18),
a_cote_de(H17, H18, Sol),
% 15 Le proprietaire du zebre
member(H19, Sol),
animal(zebre, H19),
nationalite(HZebre, H19),
% 16 nationalité du buveur de vin
member(H20, Sol),
boisson(vin, H20),
nationalite(HVin, H20),
maplist(writeln, Sol),
format("~nLe propriétaire du zèbre : ~w~n", [HZebre]),
format("Le buveur de vin : ~w~n", [HVin]).
Il y a cette règle qui n'est pas respectée :
7. la maison verte est a droite de la blanche
Or c'est la rouge qui est à droite de la verte dans ton résultat.
La maison verte est bien à droite de la blanche, être à droite ne signifie pas être juste à côté, comme je l'ai déjà dit dans mon précédent post, je l'ai volontairement codé ainsi.
Ce qui "m'ennuie" dans ton code ce sont ces rajouts :
test(L,_,_,blanche,_,_,_), % Une maison peut-être blanche
test(L,_,_,bleue,_,_,_), % Une maison peut-être bleue
test(L,_,_,_,_,_,renard), % On peut posséder un renard
test(L,_,_,_,_,docteur,_), % On peut être docteur
test(L,_,_,_,_,_,cheval), % On peut posséder un cheval
test(L,_,_,_,_,diplomate,_), % On peut être diplomate
Il n'y a pas à les rajouter, les faits indiqués sont suffisants pour obtenir la solution, il faut simplement rajouter les questions relatives au Zèbre et au vin, car ils ne sont pas évoqués dans les faits. J'ai d'ailleurs corrigé mon post pour que ce soit plus claiR.
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
C'est le principe de Prolog, Prolog travaille avec une base de faits et des règles.
A partir de là, par backtrack, il déduit toutes les réponses possibles à la question posées.
[edit]Bon, j'ai trouvé pourquoi je n'obtenais pas ta solution avec ma version : une erreur de nommage de variable + le fait que je faisais afficher une solution alors que pour les avoir toutes il fallait que je demande resolution(M1,M2,M3,M4,M5) !
D'autre part, si on oblige à ce que la maison soit juste à côté pour "à droite" alors il n'y a qu'une seule solution effectivement, sinon il y en a plusieurs.
l' énoncé N°7 devrait être "la maison verte est juste à droite de la blanche".
[/edit]
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.
Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre. En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.
Au lieu de déterrer un sujet il est préférable :
soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
soit de créer un nouveau sujet décrivant votre propre contexte
ne pas répondre à un déterrage et le signaler à la modération
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !