Solving the River Crossing Puzzle with Go
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.
Listing 6
solver.go
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.

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.
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.

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.
Infos
- River crossing puzzle: https://en.wikipedia.org/wiki/River_crossing_puzzle
- "Classic Computer Science Problems in Python": https://www.manning.com/books/classic-computer-science-problems-in-python
- All listings for this article: ftp://ftp.linux-magazine.com/pub/listings/linux-magazine.com/232/
- In-place algorithms https://en.wikipedia.org/wiki/In-place_algorithm
- Breadth-first search: https://en.wikipedia.org/wiki/Breadth-first_search
« Previous 1 2 3
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you've found an article to be beneficial.
News
-
PipeWire 1.0 Officially Released
PipeWire was created to take the place of the oft-troubled PulseAudio and has finally reached the 1.0 status as a major update with plenty of improvements and the usual bug fixes.
-
Rocky Linux 9.3 Available for Download
The latest version of the RHEL alternative is now available and brings back cloud and container images for ppc64le along with plenty of new features and fixes.
-
Ubuntu Budgie Shifts How to Tackle Wayland
Ubuntu Budgie has yet to make the switch to Wayland but with a change in approaches, they're finally on track to making it happen.
-
TUXEDO's New Ultraportable Linux Workstation Released
The TUXEDO Pulse 14 blends portability with power, thanks to the AMD Ryzen 7 7840HS CPU.
-
AlmaLinux Will No Longer Be "Just Another RHEL Clone"
With the release of AlmaLinux 9.3, the distribution will be built entirely from upstream sources.
-
elementary OS 8 Has a Big Surprise in Store
When elementary OS 8 finally arrives, it will not only be based on Ubuntu 24.04 but it will also default to Wayland for better performance and security.
-
OpenELA Releases Enterprise Linux Source Code
With Red Hat restricting the source for RHEL, it was only a matter of time before those who depended on that source struck out on their own.
-
StripedFly Malware Hiding in Plain Sight as a Cryptocurrency Miner
A rather deceptive piece of malware has infected 1 million Windows and Linux hosts since 2017.
-
Experimental Wayland Support Planned for Linux Mint 21.3
As with most Linux distributions, the migration to Wayland is in full force. While some distributions have already made the move, Linux Mint has been a bit slower to do so.
-
Window Maker Live 0.96.0-0 Released
If you're a fan of the Window Maker window manager, there's a new official release of the Linux distribution that champions the old-school user interface.