Barbara Kaskosz and I just made a new addition to the “Brain Puzzle” section of the Android Market. If you have an Android phone, go to the Market and search for either GraphSlider or flashandmath, and you will be able to download (free!) the puzzle app. Those interested in Flash programming will be happy to see the complete source code given at flashandmath.com.
In this app a mathematical graph with 5 to 8 nodes is given. Each node is labeled 0,1, 2, 3, … around the outside, and there are numbered sliding tiles within all but one of the nodes. A “move” slides the tile from its current node to an empty node along an edge of the graph, and the puzzle is solved once each numbered tile matches the label of the node it is on.
The puzzle itself is based on a general class of puzzles of which the famous “Fifteen Puzzle” is a member. The more general class was discussed in a seminal paper by Rick Wilson in 1974. In this paper, Wilson proves that for graphs with a minimal set of conditions, every possible puzzle (i.e., starting configurations of the tiles) can be solved if and only if the graph is not bipartite. If the graph is bipartite, then the puzzle is still solvable when the starting configuration is an even permutation of the final configurations.
The Fifteen Puzzle has an underlying graph that is bipartite, and this is the reason that switching two tiles (an odd permutation!) in the final configuration leads to an unsolvable puzzle. This simple fact, finally proven in general by Wilson in 1974, caused quite a stir in the late nineteenth century, as documented in Slocum’s excellent book on the Fifteen Puzzle.