### 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:

- Frogs can move one space into the empty pad or jump over one frog to
land on the empty pad.
- 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