3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$
    – Optidad
    May 29 '19 at 12:14
  • $\begingroup$ @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. $\endgroup$
    – james F.
    May 29 '19 at 12:17
  • 1
    $\begingroup$ 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." $\endgroup$ May 29 '19 at 15:39
3
$\begingroup$

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.

enter image description here

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – james F.
    May 29 '19 at 13:32
  • $\begingroup$ what $M_0$ and $K_0$ do you have ? $\endgroup$
    – Optidad
    May 29 '19 at 13:38
  • $\begingroup$ I'm working with 3 (both) for now $\endgroup$
    – james F.
    May 29 '19 at 13:41
  • $\begingroup$ 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. $\endgroup$
    – Optidad
    May 29 '19 at 13:46
  • $\begingroup$ 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? $\endgroup$
    – james F.
    May 29 '19 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.