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

© Lead Image by am not, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=18656684

Article from Issue 232/2020
Author(s):

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.

[...]

Use Express-Checkout link below to read the full article (PDF).

Buy this article as PDF

Express-Checkout as PDF
Price $2.95
(incl. VAT)

Buy Linux Magazine

SINGLE ISSUES
 
SUBSCRIPTIONS
 
TABLET & SMARTPHONE APPS
Get it on Google Play

US / Canada

Get it on Google Play

UK / Australia

Related content

  • Novell Appoints Tim Wolfe as President, Novell Americas

    Novell today appointed Tim Wolfe as president, Novell Americas, responsible for the execution of Novell's strategy across the Americas. Wolfe, who brings nearly three decades of software, technology and consulting leadership experience to the role, most recently held the position of vice president and general manager of Novell's East region in the United States. He will play a key role in Novell's transition to a greater focus on customers and partners in implementing the company's go-to-market strategy.

  • Phusion Releases Passenger Enterprise 4

    Phusion Passenger 4 offers improved scalability, Python WSGI support, multithreading, and better error diagnostics.

  • Tech Tools
    • Community Edition of ownCloud Released
    • Phusion Releases Passenger Enterprise 4
    • VMware Announces Micro Cloud Foundry Changes
  • OLPC Computers for Palestinian Refugee Children

    The United Nations Relief and Works Agency for Palestine Refugees in the Near East (UNRWA) has instituted a three-year program together with Sugar Labs and the One Laptop Per Child (OLPC) program.

  • Digital IC Simulation on Linux

    Designing field-programmable gate arrays is only half the job: The hardest part is the simulation, but Linux is the best place to tackle certain challenges.

comments powered by Disqus
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.

Learn More

News