Fernando J. Pereda

There is a traditional puzzle where 3 missionaries and 3 cannibals have to cross a river using a small canoe. Rules are:

* You cannot have more cannibals than missionaries in either bank because cannibals will eat missionaries.
* The canoe can be run by either one or two persons. Both cannibals and missionaries know how to run it.

This puzzle is really easy to solve either by hand or programming. However, hacking a script to solve it is always more challenging than solving it by hand. Juanjo proposes a solution using Ruby in Misioneros y caníbales (in Spanish). I thought I could try solving it in Haskell.

It's been really easy to solve it in Haskell given the nature of the language. The proposed solution is a specific application of a computation over graphs:

The goal is finding every possible route between two nodes of a network graph, and then choose the shortest one. Once you define the possible succesors of a given state problem, finding routes between two states is straightforward. One particular oddity of this problem is the fact that the network graph has loops, so the algorithm has to check for them.

The recursion step (with implicit backtracking) is not difficult at all. It will take an initial state as first argument, and a list of visited states as a second argument. Returns a list of solutions, each solution represented by a list of states (nodes in the graph).

solveStep :: ProbSt -> [ProbSt] -> [[ProbSt]]
solveStep prob probs = if problemSolved prob
                       then [prob:probs]
                       else concat [ solveStep p' (prob:probs) | p' <- nextStates prob
                                                               , p' `notElem` probs ]

Where nextStates gives a list of succesors for a given problem, and problemSolved checks if we solved the problem. Now the function to really solve the problem can be defined easily in terms of solveStep:

solveProblem :: [[ProbSt]]
solveProblem = solveStep ((3,3),(0,0),Start) []

Ok, stop talking, here is the code: MisCan.hs.

Cheers,
Ferdy