River Crossing Puzzle

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Problem Description

The farmer is taking his fox, duck and corn to market. He is currently stuck on the left bank of a major river. The good news is that he has a boat available. The bad news is that the boat will only hold him and one other item for each crossing.

He dare not leave the duck alone with the corn (corn would get eaten) or the duck alone with the fox (duck would get eaten). Also the farmer knows from prior experience that he cannot leave the corn alone on the right bank of the river since a large flock  of crows is waiting to devour it. 

Can you help the farmer get everything across the river safely?
.

Background & Techniques

Here's some brain exercise in at least three areas:

  • Bit manipulation to keep track of where the objects are and to relocate them.
  • Graphics - bitmaps embedded in a panel (although I didn't try to animate the crossing process).  Eight images representing the four objects (fox, duck, corn and boat) are just made visible and invisible as appropriate.
  • Graph searching to find a solution when the user presses  the "Show me how"  button.

Puzzle States

I chose to represent the state of the puzzle using the four low order bits of a State byte variable,   8=boat (and farmer), 4=fox, 2=duck and 1=corn.  For each of these, value 0 means left bank and 1 means right bank.  So we can see immediately that there 16  possible states 0 (binary 0000) representing the starting position with everything on the left up to the winning position, 15 (binary 1111),  when everything is on the right bank.  

With this system we can identify the valid state transitions, necessary when the computer searches for a solution.  From our current state we can flip the 8 bit only (send the boat across by itself) or flip the 8 bit and one other bit (send the boat to the other bank with a single object).  These valid transitions are kept in a 16X16 Moves boolean array with he first index representing the "from" state and the second index representing the "to" state.    So if we send the boat and the duck across from the initial state, State would change from 0 to 10 (8 bit plus 2 bit) and moves[0,10] would contain a value of "true" telling us that this is a valid move.  

A Loser boolean array identifies states thatare  losing positions.  For example 6 (binary 0110) represents the fox and duck alone on the right bank, definitely a no-no.  For the program solution search we just never go to state N if loser[N] is true.  In user play, we'll give the player a message that he lost and why if he moves to a losing position.

One other 16 entry boolean array, Visited,  keeps track of states we've visited during the program solution phase top avoid looping.   (The human player can loop for as long as he wants.)   

Bits can be turned on by adding 1,2,4 or 8 if you know that the bit is not on.  Similarly they can be turned off by subtracting 1,2,4 or 8 once you are sure that the bit is on.  If a bit needs to be set to 1 regardless of it's present state then OR can be used.  N OR 8 will turn the 8 bit on and leave the other bits unchanged.  To turn a bit off, AND the field with a mask that has 0 's in the bit positions to be turned off and 1's everywhere else. So N AND 7 will turn the 8 bit off for example.     To flip a bit, the "exclusive or", XOR, operation will do the trick.  The mask in this case need 1's in bit positions to be flipped.  N XOR 8 will flip the 8 bit from 0 to 1 or 1 to 0.   Bits can be tested in a loop by setting a Mask to 1 and using SHL (shift left) to move the position to be tested by one position to the left each time through the loop.  You'll find most of these techniques used here.

Graphics

The idea for the graphics was borrowed from this Strawberry McCaw puzzle page.  (also some of the images although I did find a different fox and duck).  Thanks Strawberry.   A little stretching, cropping, etc. produced 7 usable images:  fox, duck, corn without birds, corn with birds (right bank image), boat, tree-line, and river.    The fox, duck and boat  appear twice, left and right banks, but not visible at the same time.  So the TPanel used to contain the picture has a total of 10 TImage controls.  For user play, two OnClick exits handle left and right images.  Left side images are named  LEFTxxx so we can use a common routine to handle the OnClick event performing such common tasks as making sure that the boat is on the left side, making the left boat image invisible and the right boat  image visible, setting sender image to invisible, checking for winning/losing position after the move, etc.  Additionally, tests like If Sender is LeftFox then ..   are used to set the right corresponding image to visible and adjust the State value.   Procedure  CheckLoser checks for losing (and winning) states and issues messages and changes mode value as appropriate. 

Computer Solution 

To solve the puzzle programmatically we'll use recursive calls to a MakeMoves procedure which takes a "From" state and a Path stringlist as inputs and searches for an unvisited "to" state that is a valid move from this state and not a losing position.  If one is found, mark it as visited, add it to the path and call MakeMoves again with  the new state as "from".  We'll stop and return true if State equals15 (every thing on the right).  We'll return false if no unvisited states remain.  It works like magic and still  surprises me the first time I see the solution displayed.  

Running/Exploring the Program 

Suggestions for Further Explorations

Thisr problem  is perhaps the simplest of a class of river crossing problems.  Try coding solutions for

  •  "Cannibals and Missionaries" (three of each, boat holds 2, if cannibals outnumber the missionaries they'll eat them).  
  • "Jealous Husbands and Wives" - three couples,  each, boat holds 2 people at most,  no wife can be left with any man unless her husband is also present.

 

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.