Cabbage, goat, and wolf puzzle

A puzzle which pops up in a lot of books, including The Art of Prolog by Leon Sterling and Ehud Shapiro in chapter 20 Search Techniques, is the farmer who needs to get a cabbage, a goat, and a wolf to the opposite side of a river and his boat can only hold himself and one of the three at a time.

I found this a good introductory problem to write myself in GDL, thanks to having the textbook's alternative solution as guidance, and then generate a state space diagram using Graphviz.

State space diagram of cabbage, goat and wolf puzzle

Similarly to the textbook, I pruned the state space by making moves which would result in the wolf eating the goat (or the goat eating the cabbage) illegal, rather than have a lot of "Bang! You're dead! Start again!" dead ends.

The state space diagram shows that with wrong moves made illegal, the puzzle has two solutions, neither of which offers any advantage since both require the farmer to row across the river seven times. Either a depth first or a breadth first algorithm would work, and the narrowness of the tree would give a depth first search only a slight advantage.

This is simpler than most game trees in that directions don't matter, halving the number of edges, and there are only 10 states.

Writing the state graph to a database is overkill, but a good introductory example for test driven development.

cgw.pl

role(farmer).

init(left(wolf)).
init(left(cabbage)).
init(left(goat)).
init(left(farmer)).

legal(farmer, boat(wolf)) :- true(left(farmer)), true(left(wolf)), \+((true(left(cabbage)), true(left(goat)))).
legal(farmer, boat(wolf)) :- true(right(farmer)), true(right(wolf)), \+((true(right(cabbage)), true(right(goat)))).
legal(farmer, boat(cabbage)) :- true(left(farmer)), true(left(cabbage)), \+((true(left(wolf)), true(left(goat)))).
legal(farmer, boat(cabbage)) :- true(right(farmer)), true(right(cabbage)), \+((true(right(wolf)), true(right(goat)))).
legal(farmer, boat(goat)) :- true(left(farmer)), true(left(goat)).
legal(farmer, boat(goat)) :- true(right(farmer)), true(right(goat)).
legal(farmer, boat(empty)) :- true(right(farmer)), 
                              \+((true(right(wolf)), true(right(goat)))),
                              \+((true(right(cabbage)), true(right(goat)))).
legal(farmer, boat(empty)) :- true(left(farmer)), 
                              \+((true(left(cabbage)), true(left(goat)))),
                              \+((true(left(wolf)), true(left(goat)))).

next(left(X)) :- does(farmer, boat(X)), true(right(X)).
next(right(X)) :- does(farmer, boat(X)), true(left(X)).
next(left(farmer)) :- true(right(farmer)).
next(right(farmer)) :- true(left(farmer)).
next(left(X)) :- true(left(X)), \+(next(right(X))).
next(right(X)) :- true(right(X)), \+(next(left(X))).

goal(farmer, 100) :-
  true(right(wolf)),
  true(right(cabbage)),
  true(right(goat)),
  true(right(farmer)).

goal(farmer, 0) :- \+goal(farmer, 100).

terminal :- goal(farmer, 100). 

cgw.sql

CREATE TABLE cgw_states (
    id            SERIAL PRIMARY KEY, 
    state         TEXT UNIQUE,
    reward        INTEGER,
    terminal      BOOLEAN
);

CREATE TABLE cgw_moves (
    id            SERIAL PRIMARY KEY,
    move          TEXT UNIQUE
);

CREATE TABLE cgw_nexts (
    state_id      INTEGER REFERENCES cgw_states(id),
    move_id       INTEGER REFERENCES cgw_moves(id),
    next_id       INTEGER REFERENCES cgw_states(id),
    PRIMARY KEY   (next_id, move_id)
);

CREATE VIEW cgw_transitions AS
  SELECT states.state AS state,
         cgw_moves.move AS move, 
         nexts.state AS next
  FROM cgw_states AS states,
       cgw_moves,
       cgw_states AS nexts,
       cgw_nexts
  WHERE cgw_nexts.state_id = states.id AND
        cgw_nexts.move_id = cgw_moves.id AND
        cgw_nexts.next_id = nexts.id;

CREATE FUNCTION somefunc(integer, text) RETURNS integer
AS $$
[ DECLARE
    declarations ]
BEGIN
    statements
END; 
$$ LANGUAGE plpgsql;


db_player.pl

update_state(State) :-
  retractall(true(_)),
  forall(member(X, State), assertz(true(X))).

findinit(Start) :-
  setof(Init, init(Init), Start).

add_state(State) :-
  update_state(State),
  role(Player),
  goal(Player, Reward),
  (terminal, !, Terminal = true ; Terminal = false),
  odbc_connect('postgresql', Connection, []),
  odbc_query(Connection, 'INSERT INTO cgw_states (state, reward, terminal) VALUES (\'~w\', ~w, ~w)'-[State, Reward, Terminal]),
  odbc_disconnect(Connection).

test :-
  consult('cgw.pl'),
  findinit(Start),
  add_state(Start).