# Cannibals missionaries problem - solving usings graphs

I am trying to solve the cannibals - missionaries problem; we have the number of cannibals, the number of missionaries and the position of the boat. We are trying to transfer all of them to the other side, however there can't be more cannibals than missionaries on either side. The capacity of the boat is limited by 2.

There are multiple ways to solve this problem, I'm trying to do it using graphs. My questions is, how to I transform these "states" (M,K,B) into vertices in a graph? Each state represent the number of missionaries, the number of cannibals and the position of the boat.

I'm having troubles with visualization of these practical problems into graphs. Could you give me any help on how to add those vertices to the graph? Once I have the graph completed, it should be easy to solve using BFS.

• The capacity of the boat is limited ? only one person ? And by position of the boat what do you mean ? Can the boat sail empty ? May 29, 2019 at 12:14
• @Vince Hi, the capacity of the boat is limited by the number of 2, sorry. The boat can't sail empty, the position of the boat is a number 1 or 2, depending on which shore the boat is. May 29, 2019 at 12:17
• Actually there is an expository paper on the topic. Graphical Solution of Difficult Crossing Puzzles R. Fraley, K.L. Cooke and P. Detrick Mathematics Magazine Vol. 39, No. 3 (May, 1966), pp. 151-157. Available free online. "In this article we present a graphical method for solving `difficult crossing' puzzles such as the cannibals and missionaries puzzle or the puzzle of jealous husbands. The method is extremely simple and makes the solution of many such puzzle easy and quick." May 29, 2019 at 15:39

You did most of the job. Each vertex is a state $$(M, K, B)$$ and edges represent the possibility to pass from a state to another with one ship transport. Let say $$B$$ can take the values $$L$$ or $$R$$ for left and right edges respectively. $$K$$ is the number of cannibals on left edge and $$B$$, the number of monks on left edge. Initially all monks and cannibals are on left edge with the boat: state is $$(M_0, K_0, L)$$. Note that for any state there are $$M_0-M$$ monks and $$K_0-K$$ cannibals on right edge.

You can notice that any ship transport would change $$B$$ value from $$L$$ to $$R$$ or vice-versa. Thus your state graph is a bipartite graph. It changes nothing to the problem, but it is interesting to notice it.

Concerning $$K$$ and $$M$$, to respect the "cannibal constraint", a valid node must have:

• $$K \le M$$ for left edge (or $$M = 0$$),
• $$K_0-K \le M_0-M$$ for right edge (or $$M=M_0$$)

A valid left->right transport (edge) should be:

$$(M_i, K_i, L)$$ -> $$(M_i-m, K_i-k, R)$$, such that $$(m, k)$$ in $$\{(1, 0), (2, 0), (1, 1), (0, 1), (0, 2)\}$$.

and a valid right->left transport (edge) should be:

$$(M_i, K_i, R)$$ -> $$(M_i+m, K_i+k, L)$$, such that $$(m, k)$$ in $$\{(1, 0), (2, 0), (1, 1), (0, 1), (0, 2)\}$$.

Of course you must keep $$0 \le M \le M_0$$ and $$0 \le K \le K_0$$.

## BFS in the graph

So now, how to proceed ? You can create all possible vertices that is to say all $$(M, K, B)$$ with $$M \le M_0, K\le K_0, B \in {L, R})$$ that does respect the cannibals constraint. Then build all the possible edges (up to 5 from any vertex). Finally you can run the BFS in this graph to find an eventual solution. The graph would have up to $$2 M_0 K_0$$ vertices and $$10 M_0 K_0$$ edges.

A stronger solution is to build your graph as you explore it. You can express formally all states reachable from any state and check if the vertex of this state is already explored or not.

Also note that BFS is generally a good exploration method to find the shortest distance, but here you can expect left->right transports should move 2 persons and right->left transports should move only one person to decrease the left edge population.

This is indeed a good exercise for graph state representation and exploration, but after it you should try to answer these questions:

• What property between $$M_0$$, $$K_0$$ is necessary and sufficient to have a solution ? (exception of $$M_0 = 0$$)
• What is the straight forward method to find such solution ?

Here is a small example for $$M_0 = 3, K_0=2$$. In blue the edges enconutered and in red the followed one. • Thanks! I'm now trying to construct the graph, however adding all the edges is quite challenging, at least doing it within reasonable time complexity. May 29, 2019 at 13:32
• what $M_0$ and $K_0$ do you have ? May 29, 2019 at 13:38
• I'm working with 3 (both) for now May 29, 2019 at 13:41
• Why is adding the edges challenging ? Remember that from any vertex there are at most 5 edges and you know ot which nodes. What you can do is an array $M_0 \times K_0 \times 2$ to store the index of the vertices. May 29, 2019 at 13:46
• So I generated these vertexes: [0, 0, 1][0, 0, 2][0, 1, 1][0, 1, 2][0, 2, 1][0, 2, 2][0, 3, 1][0, 3, 2][1, 1, 1][1, 1, 2][2, 2, 1][2, 2, 2][3, 0, 1][3, 0, 2][3, 1, 1][3, 1, 2][3, 2, 1][3, 2, 2][3, 3, 1][3, 3, 2] and now I just add for every vertex a compatible edge? I can reduce 2 if the B parameter is 1 and I can reduce only 1, if the boar parameter is 2? May 29, 2019 at 13:54