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.

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.

StackExchange Computer Science Q#110005, answer score: 3