%fonctions utilisées. not(P):-P,!,fail. not(_). member(X,[X|_]). member(X,[_|Q]):- member(X,Q). % Representation d'un etat s(Missionnaires,Cannibales,Missionnaire_barque,Cannibale_barque,Barque). %l'état signifie que la barque est sur la rive Barque (g ou d), avec Missionnaire_barque missionnaires %Et Cannibale_barque cannibales à son bord. %Et sur la rive gauche il y a E1 Missionnaires et E2 Cannibales. % pour voir les solutions faire: resultat(S). etat_init(s(3,3,0,0,g)). etat_final(s(0,0,0,0,d)). conditions_domaine(E1,E2,B1,B2):-E1>=0, E2>=0, E1<4, E2<4, 2>=B1, B1>=0, 2>=B2, B2>=0. % / ******************************Etats acceptés*****************************/ legal(s(E1,E2,B1,B2,_)):- conditions_domaine(E1,E2,B1,B2), E1>=E2,(E2+B2)>=(E1+B1). %/ *il faut que sur la berge de gauche et sur celle de droite il y ait plus de missionnaires que de cannibales*/ legal(s(E1,E2,B1,B2,_)):- conditions_domaine(E1,E2,B1,B2), E1>=E2,E1+B1=3. % /*pas de missionnaire à droite*/ legal(s(E1,E2,B1,B2,_)):- conditions_domaine(E1,E2,B1,B2), E1=0,(E2+B2)>=B1. % /*pas de missionnaire à gauche*/ % /* 'voyage' correspond à la relation 'appliquer'*/ % /*EMBARQUEMENT à g*/ % /*barque vide*/ voyage( s(3,3,0,0,g), s(2,2,1,1,g) ). % /* 1M+1C embarquent */ voyage( s(3,2,0,0,g), s(2,1,1,1,g) ). voyage( s(3,1,0,0,g), s(2,0,1,1,g) ). voyage( s(2,2,0,0,g), s(1,1,1,1,g) ). voyage( s(2,1,0,0,g), s(1,0,1,1,g) ). voyage( s(1,1,0,0,g), s(0,0,1,1,g) ). % /**/ voyage( s(X1,3,0,0,g), s(X1,2,0,1,g) ). % /* 1C */ voyage( s(X1,2,0,0,g), s(X1,1,0,1,g) ). voyage( s(X1,1,0,0,g), s(X1,0,0,1,g) ). % /**/ voyage( s(3,X2,0,0,g), s(2,X2,1,0,g) ). % /* 1M */ voyage( s(2,X2,0,0,g), s(1,X2,1,0,g) ). voyage( s(1,X2,0,0,g), s(0,X2,1,0,g) ). % /**/ voyage( s(3,X2,0,0,g), s(1,X2,2,0,g) ). % /* 2M */ voyage( s(2,X2,0,0,g), s(0,X2,2,0,g) ). % /**/ voyage( s(X1,3,0,0,g), s(X1,1,0,2,g) ). % /* 2C */ voyage( s(X1,2,0,0,g), s(X1,0,0,2,g) ). % /**/ % /*barque avec 1M*/ voyage( s(X1,3,1,0,g), s(X1,2,1,1,g) ). % /* 1C embarque*/ voyage( s(X1,2,1,0,g), s(X1,1,1,1,g) ). voyage( s(X1,1,1,0,g), s(X1,0,1,1,g) ). % /**/ voyage( s(3,X2,1,0,g), s(2,X2,2,0,g) ). % /* 1M */ voyage( s(2,X2,1,0,g), s(1,X2,2,0,g) ). voyage( s(1,X2,1,0,g), s(0,X2,2,0,g) ). % /*barque avec 1C*/ voyage( s(3,X2,0,1,g), s(2,X2,1,1,g) ). % /* 1M embarque*/ voyage( s(2,X2,0,1,g), s(1,X2,1,1,g) ). voyage( s(1,X2,0,1,g), s(0,X2,1,1,g) ). % /**/ voyage( s(X1,3,0,1,g), s(X1,2,0,2,g) ). % /* 1C */ voyage( s(X1,2,0,1,g), s(X1,1,0,2,g) ). voyage( s(X1,1,0,1,g), s(X1,0,0,2,g) ). % /*TRAVERSEE DE g à d*/ voyage( s(X1,X2,1,1,g), s(X1,X2,1,1,d) ). % /* 1M+1C traversent */ voyage( s(X1,X2,2,0,g), s(X1,X2,2,0,d) ). % /* 2M */ voyage( s(X1,X2,1,0,g), s(X1,X2,1,0,d) ). % /* 1M */ voyage( s(X1,X2,0,2,g), s(X1,X2,0,2,d) ). % /* 2C */ voyage( s(X1,X2,0,1,g), s(X1,X2,0,1,d) ). % /* 1C */ % /*DEBARQUEMENT à d*/ voyage( s(X1,X2,1,1,d), s(X1,X2,0,0,d) ). % /* 1M+1C débarquent */ voyage( s(X1,X2,1,1,d), s(X1,X2,1,0,d) ). % /* 1C */ voyage( s(X1,X2,1,1,d), s(X1,X2,0,1,d) ). % /* 1M */ voyage( s(X1,X2,2,0,d), s(X1,X2,0,0,d) ). % /* 2M débarquent*/ voyage( s(X1,X2,2,0,d), s(X1,X2,1,0,d) ). % /* 1M */ voyage( s(X1,X2,1,0,d), s(X1,X2,0,0,d) ). % /* 1M débarque*/ voyage( s(X1,X2,0,2,d), s(X1,X2,0,0,d) ). % /* 2C débarquent*/ voyage( s(X1,X2,0,2,d), s(X1,X2,0,1,d) ). % /* 1C */ voyage( s(X1,X2,0,1,d), s(X1,X2,0,0,d) ). % /* 1C débarque*/ % /*EMBARQUEMENT à d*/ voyage( s(X1,X2,0,0,d), s(X1,X2,1,1,d) ). % /* 1M+1C embarquent */ voyage( s(X1,X2,0,0,d), s(X1,X2,1,0,d) ). % /* 1C */ voyage( s(X1,X2,0,0,d), s(X1,X2,0,1,d) ). % /* 1M */ voyage( s(X1,X2,0,0,d), s(X1,X2,2,0,d) ). % /* 2M */ voyage( s(X1,X2,0,0,d), s(X1,X2,0,2,d) ). % /* 2C */ voyage( s(X1,X2,1,0,d), s(X1,X2,1,1,d) ). % /* 1C embarque*/ voyage( s(X1,X2,1,0,d), s(X1,X2,2,0,d) ). % /* 1M */ voyage( s(X1,X2,0,1,d), s(X1,X2,1,1,d) ). % /* 1M embarque*/ voyage( s(X1,X2,0,1,d), s(X1,X2,0,2,d) ). % /* 1C */ % /*TRAVERSEE DE d à g*/ voyage( s(X1,X2,1,1,d), s(X1,X2,1,1,g) ). % /* 1M+1C traversent */ voyage( s(X1,X2,2,0,d), s(X1,X2,2,0,g) ). % /* 2M */ voyage( s(X1,X2,1,0,d), s(X1,X2,1,0,g) ). % /* 1M */ voyage( s(X1,X2,0,2,d), s(X1,X2,0,2,g) ). % /* 2C */ voyage( s(X1,X2,0,1,d), s(X1,X2,0,1,g) ). % /* 1C */ % /*DEBARQUEMENT à g*/ % /*1 personne à bord*/ voyage( s(2,X2,1,0,g), s(3,X2,0,0,g) ). % /* 1M debarque */ voyage( s(1,X2,1,0,g), s(2,X2,0,0,g) ). voyage( s(0,X2,1,0,g), s(1,X2,0,0,g) ). % /**/ voyage( s(X1,2,0,1,g), s(X1,3,0,0,g) ). % /* 1C */ voyage( s(X1,1,0,1,g), s(X1,2,0,0,g) ). voyage( s(X1,0,0,1,g), s(X1,1,0,0,g) ). % /**/ % /*2 personnes à bord*/ voyage( s(2,X2,2,0,g), s(3,X2,1,0,g) ). % /* 1M */ voyage( s(1,X2,2,0,g), s(2,X2,1,0,g) ). voyage( s(0,X2,2,0,g), s(1,X2,1,0,g) ). voyage( s(2,X2,1,1,g), s(3,X2,0,1,g) ). % /* 1M */ voyage( s(1,X2,1,1,g), s(2,X2,0,1,g) ). voyage( s(0,X2,1,1,g), s(1,X2,0,1,g) ). voyage( s(1,X2,2,0,g), s(3,X2,0,0,g) ). % /* 2M */ voyage( s(0,X2,2,0,g), s(2,X2,0,0,g) ). % /**/ voyage( s(X1,1,0,2,g), s(X1,3,0,0,g) ). % /* 2C */ voyage( s(X1,0,0,2,g), s(X1,2,0,0,g) ). % /**/ voyage( s(X1,2,0,2,g), s(X1,3,0,1,g) ). % /* 1C */ voyage( s(X1,1,0,2,g), s(X1,2,0,1,g) ). voyage( s(X1,0,0,2,g), s(X1,1,0,1,g) ). voyage( s(X1,2,1,1,g), s(X1,3,1,0,g) ). % /* 1C */ voyage( s(X1,1,1,1,g), s(X1,2,1,0,g) ). voyage( s(X1,0,1,1,g), s(X1,1,1,0,g) ). % /*'transition_possible' correspond à la relation 'appliquable' */ transition_possible(Etat1,Etat2):-voyage(Etat1,Etat2),legal(Etat2). solution(E,C,S):-etat_final(E),S=C. solution(E,C,S):-transition_possible(E,A),not(member(A,C)),solution(A,[A|C],S). % /*Not member permet qu'on n'est pas un état qui se répète c'est-à-dire pas de circuit dans le transbordement*/ resoudre(S):-etat_init(E),solution(E,[E],S). renverse([],[]). renverse([X|Y],Z):-renverse(Y,M),ajoute(M,[X],Z). resultat(R):-resoudre(S),renverse(S,R).