Search⌘ K
Home
Courses
Discover Ruby Programming Through Fun Examples

Farmer Crosses River Puzzle

Explore how to solve the classic farmer crosses river puzzle by applying backtracking and recursion in Ruby. Understand constraints and safety checks while manipulating data structures. Learn to design methods for moves, undo actions, and logging to find a safe solution step by step.

We'll cover the following...

Problem

A farmer wants to cross a river and take with him a wolf, a sheep, and a cabbage. There is a boat that can fit him plus either the wolf, the sheep, or the cabbage. If the wolf and the sheep are alone on one shore, the wolf will eat the sheep. If the sheep and the cabbage are alone on the shore, the sheep will eat the cabbage.

Expected output

Step 0
       [] |~~~| [:farmer, :wolf, :sheep, :cabbage]
Step 1 <= [:farmer, :sheep]
       [:farmer, :sheep] |~~~| [:wolf, :cabbage]
Step 2 [:farmer] =>
       [:sheep] |~~~| [:farmer, :wolf, :cabbage]
Step 3 <= [:farmer, :wolf]
       [:farmer, :wolf, :sheep] |~~~| [:cabbage]
Step 4 [:farmer, :sheep] =>
       [:wolf] |~~~| [:farmer, :sheep, :cabbage]
Step 5 <= [:farmer, :cabbage]
       [:farmer, :wolf, :cabbage] |~~~| [:sheep]
Step 6 [:farmer] =>
       [:wolf, :cabbage] |~~~| [:farmer, :sheep]
Step 7 <= [:farmer, :sheep]
       [:farmer, :wolf, :sheep, :cabbage] |~~~| []
Done!
Output showing the two sides of the river

Purpose

  • Use a backtracking algorithm

Analyze

Remember your first attempts on this famous puzzle, maybe like this:

  1. Move the farmer over the river, oops! Undo.

  2. Move the farmer and sheep over the river, check, good.

    1. Move farmer back, still good.

    2. Move farmer and cabbage across, OK.

    3. Move farmer back, oops! Undo.

  3. And so on.

This trial and error ...