While preparing for various interviews I came across river crossing puzzle with small variations quite often.
- There are 4 men who want to cross a bridge. They all begin on the same side. You have 17 minutes to get all of them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party, who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth; it cannot be thrown, etc. Each man walks at a different speed. A pair must walk together at the rate of the slower man’s pace. Man 1: 1 minute to cross; Man 2: 2 minutes to cross; Man 3: 5 minutes to cross; Man 4: 10 minutes to cross
- Try to carry Wolf, Goat and Cabbage across a river in a boat. You can take on the boat with you only one of them in each trip. If you leave Wolf and Goat on the same bank, Wolf will eat Goat. If you leave Goat and Cabbage on the same bank, Goat will eat Cabbage. Although, they will never eat one another while you stay with them. Make sure they all safely reach the other river bank.
- Once upon a time a farmer went to market and purchased a fox, a goose, and a bag of beans. On his way home, the farmer came to the bank of a river and hired a boat. But in crossing the river by boat, the farmer could carry only himself and a single one of his purchases – the fox, the goose, or the bag of the beans.If left alone, the fox would eat the goose, and the goose would eat the beans.The farmer’s challenge was to carry himself and his purchases to the far bank of the river, leaving each purchase intact. How did he do it?
- In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries.) The boat cannot cross the river by itself with no people on board.
- Time 0: Man 1, Man 2, Man 3, Man 4 –
- Time 2: Man 3, Man 4 – Man 1, Man 2
- Time 3: Man 1, Man 3, Man 4 – Man 2
- Time 13: Man 1, – Man 2, Man 3, Man 4
- Time 15: Man 1, Man 2 – Man 3, Man 4
- Time 17: – Man 1, Man 2, Man 3, Man 4
So the trick is to have an low cost man (Man 1 or Man 2) on the other side of the river so that once Man 3 and Man 4 are there we avoid moving them across the river.
- Man, Wolf, Goat, Cabbage –
- Wolf, Cabbage – Man, Goat
- Man, Wolf,Cabbage – Goat
- Cabbage – Man, Wolf, Goat
- Man, Goat, Cabbage – Wolf
- Goat – Man, Wolf, Cabbage
- Man, Goat – Wolf, Cabbage
- – Man, Wolf, Goat, Cabbage