[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
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:
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.
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.
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.
Suggestions for Further Explorations
Copyright © 2000-2017, Gary Darby All rights reserved.