I am searching for a better algorithm , more computational efficient, for the classical "wolf, goat and cabbage" problem, in Prolog. The algorithm below is based on BFS search for possible situations.
The Problem:
"Once upon a time a farmer went to a market and purchased a wolf, a goat, and a cabbage. On his way home, the farmer came to the bank of a river and rented a boat. But crossing the river by boat, the farmer could carry only himself and a single one of his purchases: the wolf, the goat, or the cabbage.
If left unattended together, the wolf would eat the goat, or the goat would eat the cabbage.
The farmer's challenge was to carry himself and his purchases to the far bank of the river, leaving each purchase intact. How did he do it?"
A current solution for this problem is this one:
writelist([H|T]):-
write(H), writelist(T).
empty_stack([]).
stack(Top, Stack, [Top|Stack]).
member_stack(Element, Stack):-
member(Element, Stack).
reverse_print_stack(S):-
empty_stack(S).
reverse_print_stack(S):-
stack(E, Rest, S),
reverse_print_stack(Rest),
write(E), nl.
unsafe(state(X,Y,Y,C)):-
opp(X, Y).
unsafe(state(X,W,Y,Y)):-
opp(X, Y).
move(state(X,X,G,C), state(Y,Y,G,C)):-
opp(X,Y), not(unsafe(state(Y,Y,G,C))),
writelist(['try farmer takes wolf ',Y,Y,G,C]),nl.
move(state(X,W,X,C), state(Y,W,Y,C)):-
opp(X,Y), not(unsafe(state(Y,W,Y,C))),
writelist(['try farmer takes goat ',Y,W,Y,C]),nl.
move(state(X,W,G,X), state(Y,W,G,Y)):-
opp(X,Y), not(unsafe(state(Y,W,G,Y))),
writelist(['try farmer takes cabbage ',Y,W,G,Y]),nl.
move(state(X,W,G,C), state(Y,W,G,C)):-
opp(X,Y), not(unsafe(state(Y,W,G,C))),
writelist(['try farmer takes self ',Y,W,G,C]),nl.
move(state(F,W,G,C), state(F,W,G,C)):-
writelist([' BACKTRACK from: ',F,W,G,C]),nl,fail.
path(Goal, Goal, Been_stack):-
nl, write('Solution Path is: '), nl,
reverse_print_stack(Been_stack).
path(State, Goal, Been_stack):-
move(State, Next_state),
not(member_stack(Next_state, Been_stack)),
stack(Next_state, Been_stack, New_been_stack),
path(Next_state, Goal, New_been_stack),!.
opp(e,w).
opp(w,e).
go(Start, Goal):-
empty_stack(Empty_been_stack),
stack(Start, Empty_been_stack, Been_stack),
path(Start, Goal, Been_stack).
test:-go(state(w,w,w,w), state(e,e,e,e)). ```
Here is a cleaned-up / simplified version (IMHO).
Overall, there is not much to be optimized.
It's standard Depth-First Search for a path through a state space.
For Breadth-First Search, another approach is needed.
One could try to make lookup of visited states faster than linear scanning (i.e. some kind of hashtable), but for a history of length 8 that's really not worth it.
It finds two solutions of history length 8: