Discover Ruby Programming Through Fun Examples/

...

/

Farmer Crosses River Puzzle

Farmer Crosses River Puzzle

Enhance your analytical skills by solving the “farmer crosses the river” puzzle.

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