Three and Three, Boat for Two
The puzzle
Three missionaries and three cannibals must cross a river. The boat carries at most two people and cannot cross empty - somebody must row it.
If cannibals ever outnumber missionaries on either bank, the missionaries there are eaten. How many crossings does the journey take?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
A bank with no missionaries on it is safe, however many cannibals are standing there.
Hint 2
At one point you must row a missionary and a cannibal back together - sending a single person back will not do.
Show the answer Hide the answer
Eleven crossings. The sixth one carries a missionary and a cannibal backwards together, which is the move nobody wants to make.
How to get there
Write the near bank as (missionaries, cannibals). Start at (3,3). Cross a missionary and a cannibal, leaving (2,2); row the missionary back to (3,2); cross two cannibals to (3,0); row one cannibal back to (3,1); cross two missionaries to (1,1).
Now the trap. The far bank holds (2,2) and the near bank (1,1), both safe, but every single-person return breaks one of them. The only legal move is to row a missionary and a cannibal back, returning the near bank to (2,2).
From there: cross two missionaries to (0,2); row a cannibal back to (0,3); cross two cannibals to (0,1); row a cannibal back to (0,2); cross the last two cannibals. Counting them up, that is eleven crossings, and no shorter legal sequence exists.
The technique worth keeping
When a state space is small, label the states and move through them rather than reasoning about people. The giveaway that you are on the right track is being forced into a move that looks like a retreat - in a constrained search the only legal move is the right one.