DOMAINS
  LOC   = east ; west
  STATE = state(LOC farmer,LOC wolf,LOC goat,LOC cabbage)
  PATH  = STATE*

PREDICATES
  nondeterm go(STATE,STATE)               % Start of the algorithm
  nondeterm path(STATE,STATE,PATH,PATH)   % Finds a path from one state to another
  nondeterm move(STATE,STATE)   % Transfer a system from one side to another
  opposite(LOC,LOC)             % Gives a location on the opposite side
  nondeterm unsafe(STATE)       % Gives the unsafe states
  nondeterm member(STATE,PATH)  % Checks if the state is already visited
  write_path(PATH)
  write_move(STATE,STATE)
  addlast(STATE,PATH,PATH)

CLAUSES
  go(StartState,GoalState):-
        path(StartState,GoalState,[StartState],Path),
        write("A Path solution is:\n"),
        write_path(Path).

  path(GoalState,GoalState,Path,Path):-!.                  % The final state is reached
  path(StartState,GoalState,L,P):-
    move(StartState,NState),
    not(unsafe(NState)),
    not(member(NState,L)),
    addlast(NState,L,NL),
    path(NState,GoalState,NL,P).

  unsafe( state(F,X,X,_) ):- opposite(F,X),!.  % The wolf eats the goat
  unsafe( state(F,_,X,X) ):- opposite(F,X),!.  % The goat eats the cabbage

  move(state(X,W,G,C),state(Y,W,G,C)):- opposite(X,Y). % Move FARMER
  move(state(X,X,G,C),state(Y,Y,G,C)):- opposite(X,Y). % Move FARMER + WOLF
  move(state(X,W,G,X),state(Y,W,G,Y)):- opposite(X,Y). % Move FARMER + CABBAGE
  move(state(X,W,X,C),state(Y,W,Y,C)):- opposite(X,Y). % Move FARMER + GOAT


  opposite(east,west).
  opposite(west,east).


  member(X,[X|_]):-!.
  member(X,[_|L]):- member(X,L).

  addlast(X,[],[X]):-!.
  addlast(X,[H|T1],[H|T2]):- addlast(X,T1,T2).

  write_path([_]).
  write_path([H1,H2|T]):-
        write_move(H1,H2),
        write_path([H2|T]).

  write_move( state(X,W,G,C), state(Y,W,G,C) ) :-!,
    write("The farmer crosses the river from ",X," to ",Y),nl.
  write_move( state(X,X,G,C), state(Y,Y,G,C) ) :-!,
    write("The farmer takes the Wolf from ",X," of the river to ",Y),nl.
  write_move( state(X,W,X,C), state(Y,W,Y,C) ) :-!,
    write("The farmer takes the Goat from ",X," of the river to ",Y),nl.
  write_move( state(X,W,G,X), state(Y,W,G,Y) ) :-!,
    write("The farmer takes the cabbage from ",X," of the river to ",Y),nl.

GOAL
go(state(east,east,east,east),state(west,west,west,west)),
write("solved\n").