1

I am developing a program that solves a more complicated version of the infamous puzzle 'The farmer, the fox, the goose, and the grain', which has eight components instead of four. I've already determined the solution; additionally, I've written out just the necessary states to complete the problem, like this:

move([w,w,w,w,w,w,w,w],[e,w,w,e,w,w,w,w]).
move([e,w,w,e,w,w,w,w],[w,w,w,e,w,w,w,w]).

etc.

My goal now is to have this program follow those states, chaining from one to the next, until it reaches the ultimate goal of [e,e,e,e,e,e,e,e]. To accomplish this, I have defined predicates as such:

solution([e,e,e,e,e,e,e,e],[]).
solution(Start,End) :-
    move(Start,NextConfig),
    solution(NextConfig,End).

My query is solution([w,w,w,w,w,w,w,w],[e,e,e,e,e,e,e,e]). However, this results in apparently infinite recursion. What am I missing?

false
  • 10,264
  • 13
  • 101
  • 209
draxias
  • 11
  • 1
  • That should just fail after a call to `solution([w, w, w, e, w, w, w, w],[e, e, e, e, e, e, e, e])`. Do you have more predicates other than these two 'move' and the two 'solution'? I assume by your 'etc.' you have more 'move' predicates, maybe you defined something like `move(X,Y)` with open variables? Or you have moves that define a loop and not just 'a,b' 'b,c', 'c,d'... etc. – vmg May 19 '15 at 00:03
  • There are indeed more moves; 17 in total. However, I have discovered my problem, and it was a loop: two moves start from the same configuration, yet end differently. These moves were both legal and required for finishing the problem, however one state was with the 'boat' starting on one side of the river and the other state was on the other side of the river. I have fixed it, and it now runs. – draxias May 19 '15 at 05:12

1 Answers1

1

To avoid cycles, try closure0/3

solution(S) :-
   closure0(move, S,[e,e,e,e,e,e,e,e]).
Community
  • 1
  • 1
false
  • 10,264
  • 13
  • 101
  • 209
  • By my understanding, there shouldn't be any cycles. The states are written such that there is only one path, from state(a,b) to state(b,c) etc. Obviously, if I fully understood the problem, then there wouldn't be one, so clearly there's something I'm not grasping. Additionally, this is supposed to be a fairly trivial implementation, and I am a beginner, so what you've linked is far beyond my skillset. – draxias May 18 '15 at 22:35