Prolog River Crossing

Question

So I was given an assignment to try to solve this problem in Prolog, though the teacher has only covered the basics and this is essentially the only project in Prolog. I feel like I'm over thinking it and that he's just expecting too much as a first time Prolog program.

The problem is listed below, how should I go about solving this?

Write a Prolog program that solves the word problem below. As part of the solution, it should print all the crossings, with the paddler listed first.

Tom, Jack, Bill, and Jim had to cross a river using a canoe that held only two people.
In each of the three crossings from the left to the right bank of the river, the canoe had two persons, and in each of the two crossings from the right to the left bank, the canoe had one person. Tom was unable to paddle when someone else was in the canoe with him.
Jack was unable to paddle when anyone else but Bill was in the canoe with him. Each person paddled for at least one crossing.

This is what I have so far, though it "works", it doesn't make sure that everyone paddles at least once.

state(tom(Side),jim(Side),jack(Side),bill(Side),c(Side)).
initial(state(tom(l),jim(l),jack(l),bill(l),c(l))).
final(state(tom(r),jim(r),jack(r),bill(r),c(r))).

canoe(P):-P=p.
canoe(P,C):-P=p,C=c.

bad(state(tom(W),jim(X),jack(Y),bill(Z),c(C))):-
    C=l,(W=c;X=c;Y=c;Z=c).

move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X),jack(Y),bill(Z),c(C1))):-
    ((canoe(W1),W=r,W=C,C1=m);(canoe(W),W1=l,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y),bill(Z),c(C1))):-
    ((canoe(X1),X=r,X=C,C1=m);(canoe(X),X1=l,X1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y1),bill(Z),c(C1))):-
    ((canoe(Y1),Y=r,Y=C,C1=m);(canoe(Y),Y1=l,Y1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1),Z=r,Z=C,C1=m);(canoe(Z),Z1=l,Z1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X1),jack(Y),bill(Z),c(C1))):-
    ((canoe(X1,W1),W=l,W=X,W=C,C1=m);
    (canoe(X,W),W1=r,W1=X1,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W1),jim(X),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1,W1),W=l,W=Z,W=C,C1=m);
    (canoe(Z,W),W1=r,W1=Z1,W1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y1),bill(Z),c(C1))):-
    ((canoe(X1,Y1),Y=l,Y=X,Y=C,C1=m);
    (canoe(X,Y),Y1=r,Y1=X1,Y1=C1)).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X1),jack(Y),bill(Z1),c(C1))):-
    ((canoe(Z1,X1);canoe(X1,Z1)),
     Z=l,Z=X,Z=C,C1=m);
    ((canoe(Z,X);canoe(X,Z)),Z1=r,Z1=X1,Z1=C1).
move(state(tom(W),jim(X),jack(Y),bill(Z),c(C)),
     state(tom(W),jim(X),jack(Y1),bill(Z1),c(C1))):-
    ((canoe(Y1,Z1);canoe(Z1,Y1)),
     Y=l,Y=Z,Y=C,C1=m);
    ((canoe(Y,Z);canoe(Z,Y)),Y1=r,Y1=Z1,Y1=C1).

find(Path):-initial(S),rez(S,Path).
bkt(State,Path,[Path|State]):-final(State).
bkt(State,Path,Sol):-move(State,Next),not(bad(Next)),
    not(member(Next,Path)),bkt(Next,[Path|Next],Sol).
rez(State,Sol):-bkt(State,[State],Sol).
start:-find(D),writef('%w\n',D).

Answer 1

(This answer may be too late, but since this is quite a classic problem/puzzle which has many many variants, I think it might still be useful to try and break the problem down a little bit.)

As yet stated in answers above, I think it might be a good idea to do some refactoring and try to write a simpler, more manageable model for this problem. What I mean with this is if someone asked you for example to 'quickly modify' your code to integrate let's say a fifth person to the puzzle, it wouldn't be much fun to refactor the code above.

You could start -this is just one approach to give you an idea- by encoding the configuration of the 4 men in a list, where we use an 'l' or 'r' to specify whether someone is located on the left or right side of the river bank. This would give us an initial state like so:

% Tom, Jack, Bill, and Jim are all on the left side
[l,l,l,l]

And we want to reach the goal state:

% Tom, Jack, Bill, and Jim are all on the right side
[r,r,r,r]

This gives us a model that is a lot easier to read/understand (imo).

We could then think some more about how we are going to encode actual transports between the river banks. We wrote our list configuration to specify which person is located where, so now we need a Prolog predicate that can transform one configuration into another. Let's say:

transport(StartState,[Persons],EndState)

Now, for the implementation, instead of explicitly matching on all possible moves (like you do in your current code), it's always a good idea to try and generalise what exactly is happening (the fun part in Prolog :) ).

Without writing too complicated code at once, we break the problem down into small pieces:

% Facts defining a crossing of the river
cross(l,r).
cross(r,l).

% Transport example for Tom
transport([X,Jack,Bill,Jim],[tom],[Y,Jack,Bill,Jim]) :- cross(X,Y).

As you can see, we now defined 'transport' in a very simple way: it is known that Tom will only cross the river on his own, so we use the cross fact to change his location. (Note that Jack, Bill and Jim are just variables stating either an 'l' or 'r' as indication on which river bank those people are located. Since Tom only crosses on his own, these variables will not change!). We could write this even more abstract and don't match specifically on 'tom', but I'm trying to keep it simple in this example.

Of course, we still need to express which crossings are valid and which aren't. From your question: "In each of the three crossings from the left to the right bank of the river, the canoe had two persons, and in each of the two crossings from the right to the left bank, the canoe had one person." These conditions can very easily be coded using our 'transport' predicate since the initial state (first arg) tells us whether we are crossing from left to right, or vice versa and our 2nd argument specifies a list of which persons are crossing. In other words, the direction of the crossing and the amount of passengers are already known and it seems a bit trivial to write down these conditions here.

Next up: "Jack was unable to paddle when anyone else but Bill was in the canoe with him." Again, this is already very easily written together in our 'transport' (note that I've used wildcards to leave out information we don't care about for this particular condition, but of course, this will probably be different in the resulting end code. It is merely to give an example.):

% Transport example for Jack (Persons length = min 1 - max 2)
transport([_,_,_,_],Persons,[_,_,_,_]) :-
    length(Persons,2),
    ( member(jack,Persons) ->
      member(bill,Persons)
    ;
      * other condition(s) *
    ).

% Alternative with pattern matching on Persons
transport([_,_,_,_],[A,B],[_,_,_,_]) :-
    * if jack is A or B, then bill is the other one *    

Another quick example: "Tom was unable to paddle when someone else was in the canoe with him."

% Tom cannot peddle in a team of 2
transport([_,_,_,_],Persons,[_,_,_,_]) :-
    length(Persons,2),
    \+ member(tom,Persons).

As you may have noticed, we have now almost completely broken down the problem in bits and pieces that can be very easily expressed in our model and we are not far from writing the actual solver. There are however enough code examples to be found online and I don't think it's necessary to work out any more of the code right here.

More inspiration can be found by searching for the classic Fox-Goose-Beans/Cabbage puzzle.

Good luck to everyone!