Skip to content

Instantly share code, notes, and snippets.

@Rhialto
Last active September 22, 2015 19:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Rhialto/7edb04c7694fbc2396dd to your computer and use it in GitHub Desktop.
Save Rhialto/7edb04c7694fbc2396dd to your computer and use it in GitHub Desktop.
Human Wolf Goat Cabbage, version 2
#!/usr/pkg/bin/swi-prolog
%
% Solve the puzzle of the wolf, the goat and the cabbage
%
% Version 2, using place(Human, Wolf, Goat, Cabbage).
:- use_module(library(lists)). % for member/2
go :-
go(Messages),
writef("%t\n", [Messages]).
go(Messages) :-
Begin = place(l, l, l, l),
Goal = place(r, r, r, r),
solve(Begin, Goal, Messages, [Begin]).
solve(State, State, [], _).
solve(From, To, [Message | Messages], History) :-
move(From, Intermediate, Message),
\+ member(Intermediate, History),
solve(Intermediate, To, Messages, [Intermediate | History]).
% The alternatives of move1 automatically pick all possibilities,
% like in pick/3 of wgc1.
% Go alone
move1(place(Hum1, Wolf, Goat, Cabb),
place(Hum2, Wolf, Goat, Cabb), go_alone(Hum2)) :-
other_side(Hum1, Hum2).
% Move wolf
move1(place(Hum1, Hum1, Goat, Cabb),
place(Hum2, Hum2, Goat, Cabb), move_wolf(Hum2)) :-
other_side(Hum1, Hum2).
% Move goat
move1(place(Hum1, Wolf, Hum1, Cabb),
place(Hum2, Wolf, Hum2, Cabb), move_goat(Hum2)) :-
other_side(Hum1, Hum2).
% Move cabbage
move1(place(Hum1, Wolf, Goat, Hum1),
place(Hum2, Wolf, Goat, Hum2), move_cabbage(Hum2)) :-
other_side(Hum1, Hum2).
other_side(l, r).
other_side(r, l).
% move moves one object from one side to the other
% and checks that this is safe.
% OR
% it moves nothing, in which case the boat only transports
% the human.
move(From, To, Message) :-
move1(From, To, Message),
safe(To).
%
% C
% G
% G C UNSAFE (alternative 1)
% W
% W C
% W G UNSAFE (alternative 2)
% W G C UNSAFE (alternative 2, Cabbage is a Don't Care)
% H
% H C
% H G
% H G C
% H W
% H W C
% H W G
% H W G C
safe(place(Hum, Wolf, Goat, Cabb)) :-
\+ unsafe(Hum, Wolf, Goat, Cabb).
unsafe(HumWolf, HumWolf, GoatCabb, GoatCabb) :- other_side(HumWolf, GoatCabb).
unsafe(Hum, WolfGoat, WolfGoat, _) :- other_side(Hum, WolfGoat).
% vim:syntax=prolog
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment