/*********************************************************************************/
/**                                                          	     		**/
/**                                                          	     		**/
/**  Zastosowanie programowania w logice do poszukiwania sciezki w grafie na    **/
/**  przykladzie problemu przewozu przez rzeke wilka, kozy i kapusty.           **/
/**                                                          	     		**/
/**  Problem polega na znalezieniu sposobu bezpiecznego przewiezienia wilka,    **/
/**  kozy i kapusty z lewego brzegu rzeki prawy, przy nastepujacych             **/
/**  zalozeniach:                                                               **/
/**  1. W lodzi jest miejsce dla przewoznika oraz dla co najwyzej jednego z     **/
/**     przewozonych obiektow.                                                  **/
/**  2. Nie wolno pozostawic po tej samej stronie rzeki, bez nadzoru            **/
/**     przewoznika, wilka z koza lub kozy z kapusta.                           **/
/**                                                          	     		**/
/**  Rozwiazanie problemu ma postac listy stanow, z ktorych kazdy opisuje       **/
/**  polozenie wilka, kozy, kapusty i przewoznika po lewej albo prawej stronie  **/
/**  rzeki. Kazdy stan jest reprezentowany przez liste stalych, ktorej kolejne  **/
/**  elementy oznaczaja odpowiednio przewoznika, wilka, koze oraz kapuste.      **/
/**  Stala 'r' odpowiada polozeniu danego obiektu na prawym brzegu rzeki a      **/
/**  stala 'l' polozeniu obiektu brzegu lewym. Przykladowo, lista [l,r,l,r]     **/
/**  reprezentuje stan, w ktorym przewoznik i koza znajduja sie na              **/
/**  lewym brzegu, a wilk i kapusta na brzegu prawym.                           **/
/**                                                          	     		**/
/**  Zapytanie o rozwiazanie: ?- solve([l,l,l,l],[r,r,r,r],P).                  **/
/**                                                          	     		**/
/*********************************************************************************/


solve(B,E,P):-
	path(B,E,[B],P1),
	reverse(P1,P).

path(E,E,W,W).
path(B,E,Wp,W):-
	next_state(B,B1),
	not(member(B1,Wp)),
	path(B1,E,[B1|Wp],W).

next_state(S,S1):-
	possible(S,S1),
        not(unsafe(S1)).

possible([X,W,G,C],[Y,W,G,C]):- opposite(X,Y).
possible([X,X,G,C],[Y,Y,G,C]):- opposite(X,Y).
possible([X,W,X,C],[Y,W,Y,C]):- opposite(X,Y).
possible([X,W,G,X],[Y,W,G,Y]):- opposite(X,Y).

unsafe([F,X,X,_]):- opposite(F,X).
unsafe([F,_,X,X]):- opposite(F,X).

opposite(l,r).
opposite(r,l).