Problem of the Month (July 2000)

A popular type of puzzle is the sliding puzzle, in which identical pieces slide in some tray, and the goal is to reach a certain configuration. The most famous of these puzzles is Loyd's "15 puzzle", shown below.

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?

ANSWERS

Joseph DeVincentis found that the Cayley graph of an n-cycle with (n–1) pieces is an n(n–1)-cycle.

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.