[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionThe 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. Background & TechniquesHere's some brain exercise in at least three areas:
Puzzle StatesI 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. GraphicsThe 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 SolutionTo 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 ExplorationsThisr problem is perhaps the simplest of a class of river crossing problems. Try coding solutions for
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |