|Here we describe what
motivated our creating the ladybugCheats Applet,
which is a modified version of Ken Perlin's Ladybug
Game. Copyright 2001 by Ken Perlin.
Our Solution Phase 1
We felt that the Ladybug Game was incredibly cool visually, but that in order to solve it by finding a complete path, we really wanted to be able to get our hands on the pieces without the ladybug cruising around. So, we almost immediately did a screen capture on the initial state of the game and used this to create our own cardboard game pieces, which we also numbered from 1 to 15 as in the standard 15 puzzle. Using the ladybug applet we had been able to quickly get within 2 tiles of a complete path through all the tiles. So, we decided to use our tactile version to do cheat rearranging until we could modify our almost-solution into a complete solution. We found a couple pretty quickly but it turned out that neither were reachable from the initial configuration, since their 15 puzzle inversion sums were both odd (i.e. corresponded to odd permutations, but the only solutions reachable from the initial configuration must be even permutations and hence must have even inversion sums).
Our Solution Phase 2
Next, we decided to completely ignore closeness to the initial configuration and instead to really cheat. So, we took all the puzzle pieces and just tried to arrange them in the most intuitive way that would yield a complete path through all the tiles. The first one we found again turned out to have an odd inversion sum, but fortunately it turned out that we could invert 2 adjacent tiles and still have a complete path. Hence, we found our first solution! Now, the 15 puzzle tile numbers for this solution were of course in scrambled order, and so we just rearranged the pieces by hand and recorded all our moves. Then in order to solve the ladybug applet puzzle we simply cheated by applying the reverse moves in reverse order.
Our Solution Phase 3
After finding our first solution, we then were able to find various symmetries of it that preserved a complete path and used these to generate many more solutions. We continue to work on various questions including finding all solutions, the least number of moves to obtain each one, finding all complete-path preserving symmetries of a given solution, and the general analysis of such create-your-own-path 15 puzzles. What great fun !!
& kids Summer 2002