Jumping Frogs

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

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

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

Search DelphiForFun.org only

 

 

 

Problem Description

Someone sent me the "Jumping Frogs" puzzle a while ago:

Six frogs on seven lily pads which must exchange places, the three on the left end up on the right and those on the right end up on the left. The rules are:

  1. Frogs can move one space into the empty pad or jump over one frog to land on the empty pad.
  2. Frogs cannot turn around and only move or jump in the direction they are facing.

Background & Techniques

Search the web for "Jumping Frogs Puzzle" to find online playable versions. A popular one is an Excel XLS file using Flash.  It is purported to be French but the language is Portuguese (and if you save the file and check properties, Author and Company appear to be Chinese characters).  Note that Vista and/or IE8 warned me me that the game wanted to contact the Internet after I solved the puzzle.  I declined the offer.

You can try your hand at my simple graphics version by clicking on the frog to move. My version has the advantage that you can undo the last move by clicking on the blank space.

There is also a "Show me" button which solves the puzzle by searching though possible sequences of moves.

Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

Programmer's Notes:

This program is mainly a check of my TGraphList class in the library UGraphSearch unit to see how many solutions exist. There seems to be only two solutions, mirror images of each other. Of the 5040 (7!) permutations, the 6 arrangements of the right facing frogs times the 6 arrangements of the left facing frogs reduces the total number of unique permutations by a factor of 36 (to 140 arrangements).

As a refresher, here's the idea of using a graph search to solve a puzzle.  If we imagine puzzle states as "nodes" (corners) of a graph, we can also imagine "edges" (lines) to each node which represent a possible state after a frog moves.   We can then search for a path along edges connecting a starting node with the desired final node.  Using LLL_RRR as the starting node and RRR_LLL as the goal node, TGraphList has procedures to search "depth-first" or "breadth-first".  Depth-first follows each possible path as far as it will go looking for the goal node and backtracking as necessary when we hit a dead end.  Breadth-first searches try all possible first moves, then all possible second moves extending all possible paths looking for one that reaches the goal node.  Depth-first searches are generally faster, but the solution found may not be the  shortest one.  Breadth-first searches guarantee that no shorter solution exists, but may take longer to find.   For this small problem the differences are not significant.      

Our UComboV2 unit contains the TComboSet class which provides the code to generate the 5040 permutations.  Of these we add only the unique ones to a string-list.  We then process the list calling the AddNode procedure for each to Graph, our TGraphList instance.  We next process the nodes just added to generate the node  after a valid frog move or jump and call the AddEdge procedure to connect those two nodes.  

The rest is simple, we just call Graph.MakePathsToDF (depth-first search) or Graph.MakePathsToBF (breadth-first search) which in turn calls our GoalFound procedure when a solution is found.

For manual solution searches, we detect user clicks on StringGrid1, a TStringGrid control which displays the frog images.  This code is in the OnSelectCell exit which passes the column and row clicked.  In our case, we have 7 columns and only a single row.  Initially we load the grid cells with the starting frog positions (LLL_RRR) one character in each cell.  When the user clicks a cell, we check to see if that frog can validly move to the cell containing the space block ( the '_') .  If so we call MakeMove, a procedure also used by GoalFound to animate the move  and display the new position in TMemo Memo1. If the user clicks the blank space and one or more moves have been made, the move is :"undone" by setting the frogs to the next-to-last position listed in Memo1.

October 29, 2009:   We placed another rung in ladder to understanding of DPI scaling yesterday.  The original October 25 posting truncated the frog display on systems with 1:1 scaling because the 1.5:1 scaling on my system  increased the size of the frog images, but not the size of the TStringGrid used to hold the frogs.  I believe that it has been corrected by inserting code in the FormAcitvate method to resize the Stringgrid1 DefaulRowWidth and DefaultColHeight  properties to match the frog image size and also to chnage change the grid Height to the frog image height and the Width to  hold 7 images. 

Let me know if problems still exist on any downloaded version on or after today's date.     

 

Running/Exploring the Program 

bulletDownload source
bulletTo recompile, you'll need UComboV2 and UGraphSearch both contained in any recent version of our DFFLibrary  (current library  is DFFLibV13) DFFLibV15
bulletDownload  executable

Suggestions for Further Explorations

Better animation to make frogs appear to "jump" and "move".
 
 
 
   
   

 

Original: October 25, 2009

Modified:  May 15, 2018

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