/*
descrizione degli stati:

s(Ms,Cs,Bs,Md,Cd,Bd)

dove 
     Ms : numero missionari sulla riva sinistra (0-3)
     Cs : numero di cannibali sulla riva sinistra (0-3)
     Bs : c' e' la barca sulla riva sinistra (0/1)
     Md : numero missionari sulla riva destraa (0-3)
     Cd : numero di cannibali sulla riva destrA (0-3)
     Bd : c' e' la barca sulla riva destra (0/1)
 
stato iniziale (Missionari, cannibali, barca sulla riva sinistra)

s(3,3,1,0,0,0)



stato finale:

s(0,0,0,3,3,1) (Missionari, cannibali, barca sulla riva sinistra)


*/


/*
Unoi stato e` sicuro se il numero dei cannibali non supera quello 
dei missionari su ciascuna riva
*/


sicuro(s(Ms,Cs,_Bs,Md,Cd,_Bd)) :-
    Ms > 0, Ms >= Cs, Md > 0, Md >= Cd.
sicuro(s(Ms,_Cs,_Bs,Md,Cd,_Bd)) :-
    Ms = 0, Md > 0, Md >= Cd.
sicuro(s(Ms,Cs,_Bs,Md,_Cd,_Bd)) :-
    Ms > 0, Ms >= Cs, Md = 0.




/*
attraversa(Stato1,Stato2) 

rappresenta un attraversamento del fiume ci sono 10 possibili operatori:

               c  ->       <-  c
               cc ->       <- cc 
               m  ->       <-  m
               mm ->       <- mm
               mc ->       <- mc
*/


% da sinistra a destra
% c   ->
attraversa(s(Ms,Cs1,1,Md,Cd1,0),s(Ms,Cs2,0,Md,Cd2,1)) :-                     
    Cs1 > 0, Cs2 is Cs1 - 1 , Cd2 is Cd1 + 1,  sicuro( s(Ms,Cs2,0,Md,Cd2,1)).
% cc  ->
attraversa(s(Ms,Cs1,1,Md,Cd1,0),s(Ms,Cs2,0,Md,Cd2,1)) :-                     
    Cs1 > 1, Cs2 is Cs1 - 2 , Cd2 is Cd1 + 2,  sicuro( s(Ms,Cs2,0,Md,Cd2,1)). 

% m   ->
attraversa(s(Ms1,Cs,1,Md1,Cd,0),s(Ms2,Cs,0,Md2,Cd,1)) :-                     
    Ms1 > 0, Ms2 is Ms1 - 1 , Md2 is Md1 + 1,  sicuro( s(Ms2,Cs,0,Md2,Cd,1)).

% mm   ->
attraversa(s(Ms1,Cs,1,Md1,Cd,0),s(Ms2,Cs,0,Md2,Cd,1)) :-                     
    Ms1 > 1, Ms2 is Ms1 - 2 , Md2 is Md1 + 2,  sicuro( s(Ms2,Cs,0,Md2,Cd,1)).

% mc  ->
attraversa(s(Ms1,Cs1,1,Md1,Cd1,0),s(Ms2,Cs2,0,Md2,Cd2,1)) :-                     
    Cs1 > 0, Ms1 > 0, 
    Cs2 is Cs1 - 1 , Cd2 is Cd1 + 1, Ms2 is Ms1 - 1 , Md2 is Md1 + 1,  
    sicuro( s(Ms2,Cs2,0,Md2,Cd2,1)).

% da destra a sinistra  
% c   <-
attraversa(s(Ms,Cs1,0,Md,Cd1,1),s(Ms,Cs2,1,Md,Cd2,0)) :-                     
    Cd1 > 0, Cs2 is Cs1 + 1 , Cd2 is Cd1 - 1,  sicuro( s(Ms,Cs2,1,Md,Cd2,0)).

% cc  <-
attraversa(s(Ms,Cs1,0,Md,Cd1,1),s(Ms,Cs2,1,Md,Cd2,0)) :-                     
    Cd1 > 1, Cs2 is Cs1 + 2 , Cd2 is Cd1 - 2,  sicuro( s(Ms,Cs2,1,Md,Cd2,0)). 

% m   <-
attraversa(s(Ms1,Cs,0,Md1,Cd,1),s(Ms2,Cs,1,Md2,Cd,0)) :-                     
    Md1 > 0, Ms2 is Ms1 + 1 , Md2 is Md1 - 1,  sicuro( s(Ms2,Cs,1,Md2,Cd,0)).

% mm   <-
attraversa(s(Ms1,Cs,0,Md1,Cd,1),s(Ms2,Cs,1,Md2,Cd,0)) :-                     
    Md1 > 1, Ms2 is Ms1 + 2 , Md2 is Md1 - 2,  sicuro( s(Ms2,Cs,1,Md2,Cd,0)).

% mc  <-
attraversa(s(Ms1,Cs1,0,Md1,Cd1,1),s(Ms2,Cs2,1,Md2,Cd2,0)) :-                     
    Cd1 > 0, Md1 > 0, 
    Cs2 is Cs1 + 1 , Cd2 is Cd1 - 1,Ms2 is Ms1 + 1 , Md2 is Md1 - 1,  
    sicuro( s(Ms2,Cs2,1,Md2,Cd2,0)).





/* stato iniziale */

iniziale(s(3,3,1,0,0,0)).

/* stato finale */

finale(s(0,0,0,3,3,1)).



risolvi(X,Y):- attraversa(X,Z),write(Z),nl,risolvi(Z,Y).

/* l' intero problema sbagliato*/
/* problema :- iniziale(S1),finale(S2),risolvi(S1,S2). */

/* una soluzione  con traccia
   la traccia e` una lista di degli stati attraversati fino ad ora
   controllanda che sposta non porti in uno stato di arrivo Z gia` presente in traccia
   si evitano i cicli
*/

risolvi(X,X,Traccia):-reverse(Traccia,TR),nl,write(TR),nl.
risolvi(X,Y,Traccia):- 
       attraversa(X,Z), not member(Z,Traccia),write(Z),nl,risolvi(Z,Y,[Z|Traccia]).

/* l' ntero problema */
problema :- iniziale(S1),finale(S2),risolvi(S1,S2,[S1]).


/* elenca le possibili soluzioni */
soluzioni :-  iniziale(S1),finale(S2),risolvi(S1,S2,[S1]), fail.

*/