Solution

All the solver in Listing 6 now needs to do is create the start state in main(), assign the ferryman and all passengers to the west bank of the river, and call solve() in line 8. There, a dynamically maintained todo list in the form of an array of state objects determines states that still need to be examined. If one of them turns out to be the target state, IsFinished() in line 25 returns a true value. If that's the case, the for loop starting in line 27 then compiles the path to this end state by tracing back the states' prev pointers. They guide the loop all the way to the start state, which has an uninitialized prev pointer (i.e., it has a value of nil in line with the Go standard). Line 32 builds an array from this inverse sequence using append() in each step to insert new elements at the beginning of the existing array, resulting in a new array.

01 package main
02
03 import (
04   "errors"
05   "fmt"
06 )
07
08 func solve(state State) ([]State, error) {
09
10   seen := make(map[string]bool)
11   todo := []State{state}
12
13   for len(todo) > 0 {
14     // pop off last element
15     lastidx := len(todo) - 1
16     s := todo[lastidx]
17     todo = todo[:lastidx]
18
19     // prevent cycles
20     if _, ok := seen[s.String()]; ok {
21       continue
22     }
23     seen[s.String()] = true
24
25     if s.IsFinished() {
26       path := []State{}
27       for cs := &s; cs.prev != nil;
28                     cs = cs.prev {
29         c := cs.Copy()
30         path = append([]State{c}, path...)
31       }
32       path = append([]State{state}, path...)
33       return path, nil
34     }
35
36     for _, succ := range s.Successors() {
37       // insert new element at end
38       succ.prev = &s
39       todo = append([]State{succ}, todo...)
40     }
41   }
42
43   return []State{},
44     errors.New("Can't solve")
45 }
46
47 func main() {
48   var state State
49
50   state.west.Add(Wolf)
51   state.west.Add(Cabbage)
52   state.west.Add(Ferryman)
53   state.west.Add(Goat)
54
55   solution, err := solve(state)
56   if err != nil {
57     panic(err)
58   }
59
60   fmt.Printf("Solution:\n")
61
62   for _, step := range solution {
63     fmt.Printf("[%s]\n", step)
64   }
65 }

Initially, the todo list only contains the start state with all participants on the west bank. The for loop from line 13 uses slice arithmetic to remove the last element of the todo array in line 17 on every round. At the end of the loop, Successors() searches for possible successors of the current state and inserts them at the beginning of the todo array slice. This creates a queue where new elements are added from the left and picked from the right (first in, last out).

This procedure causes a breadth-first search [5] in the search tree (Figure 2). It scans the nodes layer by layer until it finds the target state. If we were to use a stack instead of a queue (first in, first out), for example, by appending new states to the right of the array and also fetching them from there, this would cause depth-first behavior in the tree. The algorithm would not proceed layer by layer, but would always advance immediately to the most deeply nested paths. It might find a solution faster – but not necessarily the shortest option, and often a very convoluted one.

Figure 2: A breadth-first search examines the tree level by level and finds the shortest path to the solution. MRE, CC BY-SA 3.0

To prevent the solver from getting stuck and, for example, sending the ferryman back and forth without any cargo (therefore generating an infinite number of subsequent states in the process), line 20 checks whether a proposed subsequent state has previously been processed. To do this, it checks the seen map (a hash table) to discover whether the state's string representation already exists as a key. If so, the continue statement in line 21 ignores this entry and triggers the next round in the for loop.

Figure 3 shows the solver's output, which found a solution in seven moves. First, the ferryman takes the goat to the east bank, before coming back empty. The ferryman then takes the wolf to the east bank, but takes the goat back. When he reaches the west bank, he grabs the cabbage and leaves the goat there. He takes the cabbage to the east bank, where the wolf is waiting but is no threat to the cabbage. Now the ferryman only has to cross back without cargo and then take the goat to the east bank. The whole crew has then arrived safely without any incidents.

Figure 3: The algorithm solves the problem in seven moves.

Even More

Once programmed, the solver can also be expanded if required. How about an additional passenger who is rather mellow and won't threaten anyone, for example, a salmon? Quickly added to Listing 2's const construct as Salmon and wired into the main() function in Listing 6 with state.west.Add(Salmon), the solver will find a solution for this modified problem as well, although it will be a bit more complicated. Figure 4 shows the nine steps necessary for the entire crew to safely arrive on the eastern shore.

Figure 4: After adding a salmon to the passenger list, you can still find a solution, although it is a little more complex.

In this case, the ferryman first takes the goat, then the salmon, and then the cabbage. But now he cannot return without a cargo to the wolf waiting on the west bank, because the goat would eat the cabbage. Instead, he takes the goat back, crosses with the wolf, and then returns without cargo to pick up the goat on the west bank for the final crossing. A human puzzle fan would have tinkered with this for a while, but for the algorithm it's just another routine task, solved in a fraction of a second.

The Author

Mike Schilli works as a software engineer in the San Francisco Bay area, California. Each month in his column, which has been running since 1997, he researches practical applications of various programming languages. If you email him at mailto:mschilli@perlmeister.com he will gladly answer any questions.