Missionaries and Cannibals | Puzzles for Interview - Interview Preparation PDF Download

Introduction

The missionaries and cannibals problem is a puzzle that involves three missionaries and three cannibals who need to cross a river using a boat that can only carry two people. However, there is a constraint that if the missionaries are outnumbered by the cannibals on either side of the river, the missionaries will be eaten. In this article, we will discuss the solution to this problem.

Initial Positions

At the start of the problem, all six people are on the left side of the river. The positions are 0M (0 missionaries), 0C (0 cannibals) and 3M, 3C on the right side of the river. The boat is also on the left side.

Solution Steps

1. Send 2 cannibals to the left side of the river. The new positions are 0M, 2C and 3M, 1C on the right side. The boat is on the left side.
2. Send 1 cannibal from the left side to the right side. The new positions are 0M, 1C on the left side and 3M, 2C on the right side. The boat is on the left side.
3. Send the remaining 2 cannibals to the left side. The new positions are 0M, 3C on the left side and 3M, 0C on the right side. The boat is on the left side.
4. Send 1 cannibal from the left side to the right side. The new positions are 0M, 2C on the left side and 3M, 1C on the right side. The boat is on the left side.
5. Send 2 missionaries to the left side. The new positions are 2M, 2C on the left side and 1M, 1C on the right side. The boat is on the right side.
6. Send 1 missionary and 1 cannibal from the right side to the left side. The new positions are 1M, 1C on the left side and 2M, 2C on the right side. The boat is on the left side.
7. Send 2 missionaries to the left side. The new positions are 3M, 1C on the left side and 0M, 2C on the right side. The boat is on the right side.
8. Send 1 cannibal from the right side to the left side. The new positions are 3M, 0C on the left side and 0M, 3C on the right side. The boat is on the left side.
9. Send 2 cannibals to the left side. The new positions are 3M, 2C on the left side and 0M, 1C on the right side. The boat is on the right side.
10. Send 1 cannibal from the right side to the left side. The new positions are 3M, 1C on the left side and 0M, 2C on the right side. The boat is on the left side.
11. Send 2 cannibals to the left side. The new positions are 3M, 3C on the left side and 0M, 0C on the right side. The boat is on the right side.

Conclusion

In the final step, all six people have safely crossed the river. The boat is on the right side of the river, and the new positions are 3M, 3C on the left side and 0M, 0C on the right side.