%%% execute/0

execute(Moves):- transition(state(sheperd(a),sheep(a),wolf(a),grass(a)),
             Moves,
             [state(sheperd(a),sheep(a),wolf(a),grass(a))]).
             
%%% transition/3

transition(State,[],_):-end_state(State).
transition(State,[Move|Moves],Previous_States):- move(State,Move,NextState),
                                                 \+ member(NextState,Previous_States),
                                                 safe_state(NextState),
                                                 transition(NextState,Moves,[NextState|Previous_States]).

%%% safe_state/1

safe_state(state(sheperd(Side),sheep(Side),wolf(_),grass(_))):-!.
safe_state(state(sheperd(Side),sheep(_),wolf(Side),grass(Side))).

%%% end_state/1

end_state(state(sheperd(b),sheep(b),wolf(b),grass(b))).
             
%%% move/3

move( state(sheperd(Side_a),sheep(Location_sheep),wolf(Location_wolf),grass(Location_grass)),
go_to_other_side(Side_a,Side_b),
state(sheperd(Side_b),sheep(Location_sheep),wolf(Location_wolf),grass(Location_grass)) ):-
other_side(Side_a,Side_b).

move( state(sheperd(Side_a),sheep(Side_a),wolf(Location_wolf),grass(Location_grass)),
move_sheep(Side_a,Side_b),
state(sheperd(Side_b),sheep(Side_b),wolf(Location_wolf),grass(Location_grass)) ):-
other_side(Side_a,Side_b).

move( state(sheperd(Side_a),sheep(Location_sheep),wolf(Side_a),grass(Location_grass)),
move_wolf(Side_a,Side_b),
state(sheperd(Side_b),sheep(Location_sheep),wolf(Side_b),grass(Location_grass)) ):-
other_side(Side_a,Side_b).

move( state(sheperd(Side_a),sheep(Location_sheep),wolf(Location_wolf),grass(Side_a)),
move_grass(Side_a,Side_b),
state(sheperd(Side_b),sheep(Location_sheep),wolf(Location_wolf),grass(Side_b)) ):-
other_side(Side_a,Side_b).

%%% other_side/2

other_side(a,b).
other_side(b,a).