Wolf Goat Cabbage
This was my first attempt at illustrating graph traversal using an animated pgn. Instructions on how I did this below.
The animation is made out of 8 png files generated by graphviz’s dot as in dot -T png -o frame7.png frame7.dot. These then were combined into an animated png file using apngasm.
apngasm frame0.png frame1.png frame2.png frame3.png frame4.png frame5.png frame6.png frame7.png -d 1000 -o cgw.png
My main lesson from creating this diagram was utility values have direction, ie the utility of a node needs to be stored in the graph table with the parent and move, not just with the node itself. This is because the graph is full of cycles, and to avoid the automaton going back, the utility of going back to a node needs to be less than going forward.
Another lesson was DOT’s html shape is nifty for domain model diagrams.
A lessone I learnt writing uml.dot was graph is a reserved word which I tried to use as a label name, so needed to change to graph_table to get dot to build the png file without crashing.
Solving this puzzle involves iterative deepening to a depth limit of 6.
:- module(cabbage_goat_wolf, []).
:- thread_local true/1, does/2.
role(farmer).
init(left(cabbage)).
init(left(goat)).
init(left(wolf)).
init(left(farmer)).
init(step(1)).
legal(farmer, boat(X)) :-
true(left(farmer)),
true(left(X)),
X \== farmer.
legal(farmer, boat(X)) :-
true(right(farmer)),
true(right(X)),
X \== farmer.
legal(farmer, boat(empty)).
next(left(farmer)) :- true(right(farmer)).
next(right(farmer)) :- true(left(farmer)).
next(step(N)) :- true(step(M)), N is M + 1.
next(left(X)) :-
true(right(X)),
does(farmer, boat(X)).
next(right(X)) :-
true(left(X)),
does(farmer, boat(X)).
next(left(X)) :-
true(left(X)),
does(farmer, boat(Y)),
X \== Y,
X \== farmer.
next(right(X)) :-
true(right(X)),
does(farmer, boat(Y)),
X \== Y,
X \== farmer.
goal(farmer, 100) :-
true(right(cabbage)),
true(right(goat)),
true(right(wolf)),
true(right(farmer)), !.
goal(farmer, 0) :-
true(left(cabbage)),
true(left(goat)),
true(right(farmer)), !.
goal(farmer, 0) :-
true(left(wolf)),
true(left(goat)),
true(right(farmer)), !.
goal(farmer, 0) :-
true(right(cabbage)),
true(right(goat)),
true(left(farmer)), !.
goal(farmer, 0) :-
true(right(wolf)),
true(right(goat)),
true(left(farmer)), !.
goal(farmer, 0) :-
true(step(8)), !.
goal(farmer, 50).
terminal :-
true(right(cabbage)),
true(right(goat)),
true(right(wolf)),
true(right(farmer)).
terminal :-
true(right(cabbage)),
true(right(goat)),
true(left(farmer)).
terminal :-
true(left(cabbage)),
true(left(goat)),
true(right(farmer)).
terminal :-
true(right(goat)),
true(right(wolf)),
true(left(farmer)).
terminal :-
true(left(goat)),
true(left(wolf)),
true(right(farmer)).
utility(farmer, Value) :- goal(farmer, Value).