Three missionaries and three cannibals are on one side of a river, along with a

Question

Three missionaries and three cannibals are on one side of a river, along with a boat

that can hold one or two people. Find a way to get everyone to the other side without

ever leaving a group of missionaries in one place outnumbered by the cannibals in

that place.

a. Formulate the problem precisely, making only those distinctions necessary to en-

sure a valid solution. Draw a diagram of the complete state space.

b. Implement (in pseudocode) and solve the problem optimally using an appropriate

search algorithm. Is it a good idea to check for repeated states?

c. Why do you think people have a hard time solving this puzzle, given that the state

space is so simple?

Explanation / Answer

State space: set of cities on Romania Map
Successor function: s(x) is the set of cities adjacent to x on the map
Goal state: Bucharest
Path cost: sum of the costs of distances between the cities on the path

Each state can be characterized by listing the number of missionaries (0-3) and cannibals (0-3) on the original side of the river, and 1 or 0 to indicate whether or not the boat is on that side; it is assumed that whatever is not listed must be on the far side of the river. There are 4 x 4 x 2 = 32 states in total, but only 28 of them are accessible from the initial state (3,3,1). Twelve of these represent "dead" states in which one or more missionaries are eaten. Here is a diagram of the complete state space:

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.