Solving the River Crossing Puzzle with Go
Programming Snapshot – Go Game States
© Lead Image by am not, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=18656684
How does a ferryman transport a wolf, a goat, and a cabbage across a river in a boat that can only carry the ferryman plus one item at a time, without the wolf eating the goat or the goat eating the cabbage while left together back on shore? Mike programs the solution in Go.
Whether it is a wolf, a goat, and a cabbage, or one of the many variations on this scenario, keeping the participants safe during passage is part of the classic river crossing logic puzzle [1]. Humans find a solution to these brainteasers by trial and error. Computers, on the other hand, determine the solution by exploring trees of interlinked state sequences, eventually arriving at the desired final state by following one of many different available paths [2].
Before crossing the river, the ferryman, the wolf, the goat, and the cabbage are initially on the west bank. The ferryman can only take one of the three candidates into the boat and cross over to the east bank. During the crossing, he has to take care not to leave the wolf and goat alone on the bank, because the wolf would eat the goat. The same applies to the goat and the cabbage, as goats like to eat cabbage.
The riddle seems unsolvable at first. For example, once the ferryman has crossed the river with the goat and returns on an empty run, the only choice he has is between the wolf and the cabbage as the next candidate. However, neither will get along with the goat on the other bank. The trick is that the ferryman can also carry passengers on the return journey, thus ensuring that he never leaves a dangerous combination (goat/cabbage or wolf/goat) unattended.
[...]
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
-
Alpine Linux 3.24 Features Fresh Desktops and a Newer Kernel
If you're a fan of Alpine Linux, it's time to upgrade because the latest version has been released with KDE Plasma 6.6, Gnome 50, and Linux kernel 6.18 LTS.
-
EU Open Source Strategy Plays Key Role in Tech Sovereignty Package
Comprehensive measures adopted by the European Commission aim to reduce dependency on non-EU countries.
-
Linux Foundation Report Indicates AI Driving Tech Hiring
Within growing security and skills gaps, AI has been found to be a positive driving force behind tech hiring trends in Europe.
-
United Nations Open Source Portal Goes Live
A new open source portal seeks to coordinate and scale open source efforts across the United Nations system.
-
KDE Linux Drops AUR
KDE Linux developers have dropped the Arch User Repository from the build pipeline due to security concerns; other distributions should consider doing the same.
-
California May Exempt Linux from Its Age-Verification Law
After backlash from the Linux community, California may be backing off on its promise to force all operating systems to verify age, but one platform may still have to comply.
-
Another Logic Bug Found in Linux Kernel
Qualys has discovered a vulnerability in the Linux kernel that can be used to elevate standard user privileges.
-
Ubuntu Core 26 Offers Game-Changing Enterprise Features
Ubuntu Core 26 could be a game-changer for organizations looking for increased security and reliability.
-
AI Flooding the Linux Kernel Security Mailing List
AI is giving Linus Torvalds a headache, but not in the way you might think.
-
Top Priorities for Open Source Pros Seeking a New Job
Professional fulfillment tops the list, according to LPI report.