title: Prolog River Crossing
body: <p>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.</p>
  
  <p>The problem is listed below, how should I go about solving this?</p>
  
  <p>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.</p>
  
  <p>Tom, Jack, Bill, and Jim had to cross a river using a canoe that held only two people.<br>
  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.<br>
  Jack was unable to paddle when anyone else but Bill was in the canoe with him.  Each person paddled for at least one crossing.</p>
  
  <p>This is what I have so far, though it "works", it doesn't make sure that everyone paddles at least once.</p>
  
  <pre><code>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).
  </code></pre>