~ 1 min read

Missionaries and Cannibals Puzzle

I've encountered some interesting problem which is famous mainly because it has much to do with AI (Artificial Intelligence) development. The problem is called "Missionaries and Cannibals". The description is:

"Three missionaries and three cannibals come to a river. A rowboat that seats two is available. If the cannibals ever outnumber the missionaries on either bank of the river, the missionaries will be eaten. How shall they cross the river?''

The following statement  - "If the cannibals ever outnumber " means that cannibals can't outnumber missionaries while counting anyone in moored boat. (otherwise the problem is simple)

The problem has an elegant and pretty easy solution, yet it is usually hard to humans because humans don't do a formalization of the problem which leads to many repeated states. This issue is mainly why this problem is popular. Amarel (1971) considered several representations of the problem and discussed criteria whereby the following representation is preferred for purposes of AI and why this problem is hard for humans.

Solution