I’m… perhaps trying to learn how to use Prolog. Currently I’m attempting to solve the Missionaries and Cannibals problem – where you need to move 3 missionaries and 3 cannibals across a river and if the cannibals ever outnumber the missionaries, they eat them. A boat can be used to cross the river, and up to two people can use that boat (it needs at least 1 person on it in order to move from one side of the river to the other).

I’ve been having trouble with it, so I’ve been looking at solutions online (perhaps not the best idea). Pretty much all of them seem to only generate one solution to the problem, but I was under the impression that there’s more than 1 solution. I spoke with a friend about this and he suggested using a DFS implementation, but I don’t quite understand how to use it in a way that fits with the states utilized in the Missionaries/Cannibals problem. The solution I was looking at had this recursive solution in Prolog:

path([A,B,C],[D,E,F],Traversed,Moves) :-
   move([A,B,C],[I,J,K],Out),
   legal([I,J,K]),  % Don't use this move unless it's safe.
   not(member([I,J,K],Traversed)),
   path([I,J,K],[D,E,F],[[I,J,K]|Traversed],[ [[I,J,K],[A,B,C],Out] | Moves ]).

Legal is whether or not a move can be made without a missionary being eaten:

legal([B,A,_]) :-
   (A =< B ; B = 0),
   C is 3-A, D is 3-B,
   (C =< D; D = 0).

And move involves each of the rules dictating how the missionaries and cannibals can move.

How can I create a solution that uses DFS to generate all correct answers over recursion which only generates one solution?

I’ve run the solution code but it doesn’t exactly help me understand things too well, and my inexperience with Prolog makes it difficult for me to convert the recursive solution to a DFS one.