Cannibals and Missionaries

An old puzzle turned into a little runtime analysis programming project:

You're given a number c cannibals and m missionaries on one side of a river. In the river is a boat that can carry b people at a time. Your task is to move all the missionaries from one side of the river to the other. A valid state is one in which there are no more cannibals than missionaries on either side of the river or in the boat unless there are 0 missionaries there (on the fear that the missionaries will be overpowered and eaten). The boat must have at least one person in it to move across the river.

For instance, for [m=1, c=1, b=2] a solution is for both people to take the boat across. For [m=2, c=2, b=2] a solution is for both cannibals to take the boat, one to return, both missionaries to take the boat and have one return, then the remaining cannibal and missionary to take the boat across. For [m+c>1 and b <= 1] there is no solution.

1) Write an algorithm to quickly find any solution. What is its complexity?
2) Write an algorithm to find the fastest (fewest steps) solution. What is its complexity?
3) Write an algorithm to determine whether the state is solvable. What is its complexity?
4) Write an algorithm to find the number of steps in the fastest solution, without it being necessary to produce the solution. Is it faster than #2?
5) Write a heuristic which would provide a number of steps such that if a solution was found to use that many steps, it would be the known fastest solution. (A heuristic that satisfied this problem could simply return 1)