The Missionaries and Cannibals Problem

The Problem. Three missionaries and three cannibals on the left bank of a river seek to cross the river to the right bank. They have a boat which can carry up to two people at a time. All missionaries and cannibals are able to row the boat. If at any time the cannibals outnumber the missionaries on either bank the cannibals will eat the missionaries.

Try to solve this problem yourself.

Actions. In the SIPE-2 plan drawing, the actions are named as follows:

ROW-M-C Row 1 missionary and 1 cannibal to the other side
ROW-1-C Row 1 cannibal to the other side
ROW-2-C Row 2 cannibals to the other side
ROW-1-M Row 1 missionary to the other side
ROW-2-M Row 2 missionaries to the other side

Action arguments. If the arguments are printed, there will be a list of 4 numbers giving the situation before the action, followed by the name of the destination of the rowing (left-bank or right-bank). The first 2 numbers give the number of cannibals and missionaries (respectively) on the same bank as the boat. The last two numbers give the number of cannibals and missionaries on the opposite bank.

SIPE-2 finds 4 solutions (that do not return to a previous state) when it searches the entire space of solutions.

Click here to see the SIPE-2 input file for Missionaries and Cannibals.

Back to Wilkins Home Page Back to SIPE-2 Home Page

David E. Wilkins
Last modified: Tue May 4 18:46:15 1999