Cannibals and missionaries

A classic crossing puzzle. Good practice in keeping track of information and presenting a solution.

Puzzle

Deep in the heart of the Amazon, three missionaries traveling with three cannibals come to a river. The only way across is a small boat. The boat will only hold two people at a time, and must be rowed back and forth across the river. Complicating matters is the missionaries' firm belief that if ever they found themselves outnumbered by the cannibals on one side or the other (in the boat or on land), the cannibals would scarf them down. How can all six travelers safely cross to the other side of the river?

Variations

This time, only one of the missionaries and only one of the cannibals know how to row the boat. Does this make the problem harder or easier (or make no difference)?

Mathematical Content

One way to solve the problem is to consider every possible allowable combination of cannibals and missionaries on the near bank of the river. Let each be a vertex of a graph. Then connect any two vertices if it is possible to get from one to the other through a valid trip of the boat back and forth. Finding a solution to the problem is now as easy as finding a path through the graph.

Links

Flash game - This amusing web app lets you try out your solution. A huge help if you are stuck or have trouble keeping track of everyone.