The Problem

Two married couples want to cross a river but the only available boat's capacity is two people and both husbands are so jealous that neither one will allow his wife to be around another man unless he is present too. Design an algorithm that will get both couples across the river.

A Discussion

Let wi designate the ith wife where i's value is 1 or 2.

Let hi designate the ith husband where i's value is 1 or 2.

Let b designate the boat.

1. (b, h1, w1, h2, w2|) -> (h1, h2|b, w1, w2) is a good crossing where husband 1 and husband 2 are on the near side of the river and the boat, and wife 1 and wife 2 are on the far side of the rive.

2. (b, h1, w1, h2, w2|) -> (h1, w2|b, h2, w1) is a bad crossing because both wives are in the presence of other men without their husbands.

3. (b, h1, w1, h2, w2}) -> (b, h1, h2|w1, w2) is an impossible crossing because no one can cross the river without a boat. However, an impossible crossing is not the same as an impossible. configuration.

4. (b, h1, h2|w1, w2) is a possible configuration.

End Result:

Write a series of possible crossings that move the couples from the near side of the river to the far side of the river.

Please help. Thank You