The Puzzle

The Leapin' Lizards puzzle by Binary Arts is played with colored lizards trying to make their way home to same-colored rocks. The lizards can move only to an empty rock and only along the paths given by the graph on the card. The Binary Arts game comes with 40 cards rated from "Beginner" to "Expert." The applet linked here allows you to try the puzzle and to see the shortest possible solution for these 40 cards. To see a table of the shortest possible solutions to each of these puzzles, click here.

The Mathematics

In the 1974 paper [5], Rick Wilson proves,

"...for a finite simple nonseparable graph, with one exception, any position can be reached from any other position unless the graph is bipartite. In the bipartite case, the set of positions splits into two sets, with no position in one set reachable from a position of the other set."

This completely answers questions about "solvability," but the approach leaves open issues about strategy and structure. For example, for a given graph and starting position, what is the shortest solution? For a given graph, what is the maximum number of moves necessary to solve any solvable puzzle on that graph?

The Applet as a Teaching/Research Tool

The applet linked here can be extended by downloading the zipped files here (there will be three files when extracted, lizards.html, lizards.swf and lizards.xml) and editing the data file lizards.xml. This is a text file that can be edited with any text editor.

As long as all three files are in the same directory once posted on the website, the applet will get the data from your version of the lizards.xml file. In this file, the data fore each puzzle is specified as shown below on the left. The example shown corresponds to the puzzle on the right.

<puzzle num="40" lev="Expert">
<mat>
0,1,0,0,0,1;
1,0,0,0,1,1;
0,0,0,1,0,1;
0,0,1,0,1,0;
0,1,0,1,0,0;
1,1,1,0,0,0
</mat>

<strt>
0,5,3,2,1,4
</strt>
</puzzle>
Puzzle Number 40

In this data, the attributes num and lev can be anything, and they will show up just like this in the "Choose a puzzle" menu. The contents of the <mat>...</mat> tag specify an adjacency matrix for the six-vertex graph that makes up this particular puzzle. For example, the 1 in row 1, column 2 indicates that this puzzle has an edge from vertex 1 to vertex 0. Note that the vertices are numbered 0 through 5, with 0 being the peg at the bottom that always begins empty. The <strt>...</strt> tag specifies the starting position of the lizards. We do this by numbering the lizards 1 = red, 2 = yellow, 3 = green, 4 = blue, 5 = purple, and letting 0 stand for the empty space. Then we list the initial order of the lizards, starting at the bottom and moving clockwise round the circle.

Each subsequent puzzle can be created in the same file, and the pull down list will include all puzzles defined in the lizard.xml file.

References and Resources

  1. A. F. Archer, "A Modern Treatment of the 15 Puzzle," American Mathematical Monthly, 106, 793-799 (1999).
  2. E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning ways for your mathematical plays, Volume 4.
  3. Bogolmolny, A., Sliders, at http://www.cut-the-knot.org/pythagoras/SLIDER.shtml, accessed December 30, 2008.
  4. A. Fink and R. Guy, "Rick’s Tricky Six Puzzle: S sits specially in S", manuscript, http://math.berkeley.edu/~finka/trickysc.pdf
  5. R. M. Wilson, "Graph Puzzles, Homotopy, and the Alternating Group," J. of Combinatorial Theory Series B, 16, 86-96 (1974).