Question

From an initial position on the left bank of a river, a boatman is to transport a wolf, a goat and a
cabbage to the right bank of the river. His boat is only big enough to hold himself and one other object at a time. The wolf cannot be left alone with the goat, and the goat cannot be left alone with the cabbage. How should the boatman proceed? Describe a graph that can be used to solve the puzzle, and find a solution.

Answer 1

Question: From an initial position on the left bank of a river, a boatman is to transport a wolf, a goat and a cabbage to the right bank of the river. His boat is only big enough to hold himself and one other object at a time. The wolf cannot be left alone with the goat, and the goat cannot be left alone with the cabbage. How should the boatman proceed? Describe a graph that can be used to solve the puzzle, and find a solution.

Solution: Denote the state of the system in the following way: (X|Y), where X is the list of all elements (B – boatman, W – wolf, G – goat, C – cabbage), that are on the left bank, and Y – on the right. For example, the starting state is denoted as (BWGC|) – boatman, wolf, goat and cabbage are all on the left bank of a river. Let's find out to which states system can move after the (BWGC|).

$$(\text{BWGC} |) \rightarrow \left[ \begin{array}{l} (GC | BW) \\ (WC | BG) \\ (WG | BC) \\ (WGC | B) \end{array} \right.$$

As we can see, the states (GC|BW) and (WG|BC) are not acceptable, because in the first state, the goat is left with the cabbage and in second – the wolf is left with the goat. The state (WGC|B) is not interesting, because from it we can go only to starting state. So, the only one acceptable state is (WC|BG).

$$(\text{WC} | \text{BG}) \rightarrow \left[ \begin{array}{l} (BWC | G) \\ (BWGC |) \end{array} \right.$$

(BWC|G) and (BWGC|) are both acceptable, but (BWGC|) is the same as the starting state. Reasoning similarly, we can draw the following graph for the system states:

With the help of the graph we can easy construct the algorithm to transport B, W, G and C to the right bank.

For example, (BWGC|) -> (WC|BG) -> (W|BCG) -> (BWG|C) -> (G|BWC) -> (BG|WC) -> (BWGC).