% Auteur:
% Date: 02/02/2011

etat_initial(etat(gauche,[loup,chevre,chou],[])).
etat_final(etat(droit,[],[loup,chevre,chou])).

move(etat(gauche,G,D),X):-member(X,G).
move(etat(droit,G,D),X):-member(X,D).
move(etat(B,G,D),alone).

update(etat(B,L,R),X,etat(B1,L1,R1)):-update_bateau(B,B1),update1(X,B,L,R,L1,R1).

update_bateau(gauche,droit).
update_bateau(droit,gauche).


update1(alone,B,L,R,L,R).
update1(X,gauche,L,R,L1,R1):- select(X,L,L1),insert(X,R,R1).
update1(X,droit,L,R,L1,R1):- select(X,R,R1),insert(X,L,L1).


insert(X,[Y|Ys],[X,Y|Ys]):- precedes(X,Y).
insert(X,[Y|Ys],[Y|Zs]):- precedes(Y,X),insert(X,Ys,Zs).
insert(X,[],[X]).

precedes(loup,X).
precedes(X,chou).

legal(etat(gauche,L,R)):- not(illegal(R)).
legal(etat(droit,L,R)):- not(illegal(L)).

illegal(L):-member(loup,L),member(chevre,L).
illegal(L):-member(chevre,L),member(chou,L).

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

solve(State,History,[]):-etat_final(State),!.
solve(State,History,[Move|Moves]):- move(State,Move),update(State,Move,State1),legal(State1),
not(member(State1,History), solve(State1,[State1|History],Moves)).

test(Moves):-etat_initial(State), solve(State,[State],Moves).