Each sliding puzzle can be represented by a graph, showing the pieces as circles and possible slides with lines. For the "15 puzzle", this is shown below.
But there is another graph of a sliding puzzle called a Cayley graph. Here the vertices are different positions of the puzzle, and the edges connect two positions which are one move apart. Unfortunately, we cannot illustrate the Cayley graph for the "15 puzzle" here, since it contains 16! / 2 = 10,461,394,944,000 vertices. Instead we show the Cayley graph for the much simpler sliding puzzle shown below.
There are 12 different positions for this puzzle, and each has 2 possible moves, so the Cayley graph must be a 12-cycle. What other small sliding puzzles have interesting Cayley graphs?
He also showed that the Cayley graph of a tetrahedal puzzle with 3 pieces is the graph below:
Here are some of the Cayley graphs I found:
If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 7/22/00.