%Un senyor es troba davant d’un riu amb el seu llop, un xai i un enciam. Al riu %hi ha una canoa que li permet transportar només una casa d’un costat a l’altre. %Com s’ho ha de fer si vol creuar el riu, sabent que no pot deixar sols el llop %i el xai ni el xai i l’enciam per por a que l’un es mengés a l’altre?

%Definim l’estat com a:

% estat(     posicio: dre/esq,
%            llista d’elements a l’esquerra: l, x, e,
%            llista d’elements a la dreta)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% creuar_riu(estat inicial, llista de passos per tal de creuar)%

creuar_riu(estat(esq,[l, x, e], []), M):-
    passar_de( estat(esq,[l,x,e],[]),
    [estat(esq,[l,x,e],[])],
    estat(dre,[],[l,x,e]),
    M).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% passar_de(estat inicial, llista d’estats ja visitats, estat final, passos)%

passar_de(X,_,X,[]).

passar_de(estat(Pos,Le,Ld),LEST,Y,[Mact|M]):-
    moviment(Pos,Le,Ld,Mact,Est_dest),
    \+(member(Est_dest, LEST)),
    passar_de(Est_dest, [Est_dest|LEST], Y, M).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% moviment(posició del barquer, elements esq, element dre, Mov. Act, estat res.)

moviment(esq,Le,Ld,passa_de_esquerra_a_dreta(E),estat(dre,Lep,Ldp)):-
    member(E,Le),
    treu(E,Le,Lep),
    \+(esmengen(Lep)),
    posa(E,Ld,Ldp).

moviment(esq,Le,Ld,passa_de_esquerra_a_dreta(res),estat(dre,Le,Ld)):-
    \+(esmengen(Le)).

moviment(dre,Le,Ld,passa_de_dreta_a_esquerra(E),estat(esq,Lep,Ldp)):-
    member(E,Ld),
    treu(E,Ld,Ldp),
    \+(esmengen(Ldp)),
    posa(E,Le,Lep).

moviment(dre,Le,Ld,passa_de_dreta_a_esquerra(res),estat(esq,Le,Ld)):-
    \+(esmengen(Ld)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% treu(element, llista, llista sense l’element)%

treu(_,[],_):-fail.
treu(X,[X|Y],Y).
treu(X,[X1|Y],[X1|Y1]):-X\== X1,treu(X,Y,Y1).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% posa(element, llista, llista amb l’element ordenada)%

posa(X,[],[X]).
posa(X,[e],[X,e]).
posa(X,[l],[l,X]).
posa(e,L,Lp):-append(L,[e],Lp).
posa(l,L,[l|L]).
posa(x,[l,e],[l,x,e]).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% esmengen(menjador, menjat)%

esmengen([l,x]).
esmengen([x,e]).
esmengen([l,x,e]).

% Què hem de fer si no volem repeticions?
% Com ho podríem fer per estalviar-nos el tractament de la llista com a ordenada?