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
Digital Autonomy
• The Answer Was Already on the Shelf
• Changing the Chip Industry: How Public Investment Has Grown Open Silicon
• United Nations Open Source Portal Goes Live
• EU Open Source Strategy Plays Key Role in Tech Sovereignty Package
• France Says “Au Revoir” to Microsoft
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
-
Yet Another Linux Kernel Vulnerability Discovered
Affecting millions of systems, a kernel flaw discovered by Qualys could allow users to gain root privileges.
-
Ubuntu 26.10 to Include Ubuntu Certified Hardware Check
If you've ever wondered if your laptop or PC is officially certified to run Ubuntu, that curiosity will soon be met.
-
Substantial Update to IPFire Now Available
The lastest version of IPFire features a fundamental change to how the system handles DNS.
-
Gnome Working on Test Center App to Make Testing Easier
It's now possible to test experimental features on the Gnome desktop without worrying that you'll break things.
-
New Vulnerability Discovered in Linux Kernel
Hiding out for nearly 15 years, the Ghostlock vulnerability allows a standard logged-in user to gain root privileges.
-
New Linux Flaw Lets Attackers Escape VMs
A 16-year-old vulnerability allows an attacker to escape a virtual machine, gain access to the host, and execute malicious code.
-
Hannah Montana Linux Is Back!
Developer Noah Cagle decided the world needed the once obscure but beloved Linux distribution and gave it a decidedly pink refresh.
-
System76 Refreshes the Lemur Laptop
If you're looking for a laptop with tons of power and battery, look no further than the latest iteration of the System76 Lemur Pro.
-
More than 43 Million Lines of Code in Linux Kernel 7.2
Using the cloc utility, Michael Larabel of Phoronix discovered that Linux kernel 7.2 has over 43 million lines of code.
-
Kubuntu Focus Goes Ultra
The Kubuntu Focus team has upped the performance ante of its M2 and Zr laptops with the latest, greatest CPUs from Intel.