/*

Una possibile soluzione del Mondo dei Blocchi con ricerca 

*/


/*
descrizione degli stati:
su(a/X,b/Y,c/Z). Si intende che  a e'  sull'oggetto  X etc.
l' ordine a b c e` tassativo
gli oggetti possono essere i blocchi a, b, c o ul tavolo t

esempi:

  C
  A    B
---------------

su(a/t,b/t,c/a)


stato finale:
 A
 B
 C
-------------

su(a/b,b/c,c/t)

*/


/*
quando un oggetto X e`libero nello stato S?

a e' libero se b non e` appogiato su a e se c non e' appoggiato su a
etc.
il tavolo t e` sempre libero

*/
libero(a,S) :- S \= su(_,b/a,_), S \= su(_,_,c/a).
libero(b,S) :- S \= su(a/b,_,_),  S \= su(_,_,c/b).
libero(c,S) :- S \= su(a/c,_,_), S \= su(_,b/c,_).
libero(t,_).



/*
sposta blocco(Oggetto, StatoDiPartenza, StatoDiArrivo).

per spostare l'oggetto a dallo stato di partenza bisogna che a sia libero e che w 
(l' oggetto che su cui posare a) sia libero e distinto da a stesso.
analogo per b e c. 
*/

sposta(a,su(a/X,b/Y,c/Z),su(a/W,b/Y,c/Z)) :- 
         libero(a, su(a/X,b/Y,c/Z)), libero(W,su(a/X,b/Y,c/Z)),W\=a,W\=X.
sposta(b,su(a/X,b/Y,c/Z),su(a/X,b/W,c/Z)) :- 
         libero(b, su(a/X,b/Y,c/Z)), libero(W,su(a/X,b/Y,c/Z)),W\=b,W\=Y.
sposta(c,su(a/X,b/Y,c/Z),su(a/X,b/Y,c/W)) :- 
         libero(c, su(a/X,b/Y,c/Z)), libero(W,su(a/X,b/Y,c/Z)),W\=c,W\=Z.

/* stato iniziale */
iniziale(su(a/t,b/t,c/a)).

/* stato finale */
finale(su(a/b,b/c,c/t)).



/* una soluzione - sbagliata !!!!!  perche` contiene dei cicli */

risolvi(X,X).
risolvi(X,Y):- sposta(Blocco,X,Z),write(Blocco/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):- sposta(Blocco,X,Z), not member(Z,Traccia),write(Blocco/Z),nl,risolvi(Z,Y,[Z|Traccia]).

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


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

/*

questa e` la migliore:

[su(a / t, b / t, c / a), su(a / t, b / t, c / t), su(a / t, b / c, c / t), su(a / b, b / c, c / t)]

*/