Why doesn't Prolog find a solution for 'Fox, goose and bag of beans puzzle' and shows 'true' instead?

Question

I wanted to solve the "Fox, goose and bag of beans puzzle" with Prolog as an exercise.

So I wrote

p(left).
p(right).
valid((Man, Goose, Fox, Beans)) :- p(Man),p(Goose),p(Fox),p(Beans), Man == Goose.
valid((Man, Goose, Fox, Beans)) :- p(Man),p(Goose),p(Fox),p(Beans), Man == Beans, Goose \= Fox.
valid((Man, Goose, Fox, Beans)) :- p(Man),p(Goose),p(Fox),p(Beans), Man == Fox, Goose \= Beans.

step((Man1, Goose, Fox, Beans), "Man", (Man2, Goose, Fox, Beans)) :- 
    valid((Man1, Goose, Fox, Beans)), valid((Man2, Goose, Fox, Beans)),
    Man1 \= Man2.

step((Man1, Goose1, Fox, Beans), "Goose", (Man2, Goose2, Fox, Beans)) :- 
    valid((Man1, Goose1, Fox, Beans)), valid((Man2, Goose2, Fox, Beans)),
    Man1 \= Man2, Goose1 \= Goose2.

step((Man1, Goose, Fox1, Beans), "Fox", (Man2, Goose, Fox2, Beans)) :- 
    valid((Man1, Goose, Fox1, Beans)), valid((Man2, Goose, Fox2, Beans)),
    Man1 \= Man2, Fox1 \= Fox2.

step((Man1, Goose, Fox, Beans1), "Beans", (Man2, Goose, Fox, Beans1)) :- 
    valid((Man1, Goose, Fox, Beans1)), valid((Man2, Goose, Fox, Beans2)),
    Man1 \= Man2, Beans1 \= Beans2.

reachable(S, _,[], S).
reachable(S, Visited, [Step|Steps], Z) :- 
    step(S,Step,Tmp),valid(Tmp), not(member(Tmp,Visited)),
    reachable(Tmp, [Tmp|Visited], Steps, Z).

start((left,left,left,left)).
goal((right,right,right,right)).

solve(Steps) :- start(S), goal(Z), reachable(S, [], Steps, Z).

Question

I thought with solve(X). I would get a sequence of valid steps. But instead, I get

?- solve(X).
false.

Why don't I get a list of steps that go from start to goal?

Code explained

valid checks for a 4-tuple, where the first element is the position of "Man", the second is the position of "Goose", the third is the position of "Beans" if nobody gets eaten.

step(Situation1, Description, Situation2) makes a step from a valid situaiton to another valid situation.

reachable(Start, SituationList, Steps, Goal) checks if the situation Goal can be reached from the situation Goal while every situation in SituationList gets visited exactly once and Steps is a description what steps were taken in which order.

Answer 1

The primary issue causing the failure is a typo:

step((Man1, Goose, Fox, Beans1), "Beans", (Man2, Goose, Fox, Beans1)) :- 

Should be:

step((Man1, Goose, Fox, Beans1), 'Beans', (Man2, Goose, Fox, Beans2)) :- 

This will generate correct solutions. There are a few other clean up points:

• You are using double quotes on strings, which in Prolog, is actually a sequence of ASCII codes (prolog List). If you want a string displayed as just a string, you would use Prolog atoms which are enclosed in single quotes. So, for example, 'Man' instead of "Man".
• The goal of valid(Tmp) in your reachable/2 clause is superfluous since the prior goal of step ensures that Tmp will be valid according to the valid rule.
• In this specific application, the first of two valid goals in each step/3 clause isn't necessary since your first argument comes from a previously validated step. (It depends upon how "general" you want step/3 to behave).

Beyond that, the solve/1 still produces many duplicate results, but they are all correct and all the correct solutions are discovered.