Game graphs for Towers of Hanoi on 3 or more pegs

3-peg Towers of Hanoi

Introduction

The Towers of Hanoi is a well-known puzzle. It goes as follows: n disks of different sizes are stacked on one of three pegs, largest disk on the bottom and smallest on top:

This puzzle and some of its generalizations have been discussed in numerous books and articles. The basic puzzle is simple enough for a child to understand, while further investigation leads into some fairly hard-core mathematics. Here I stick with some of the easier stuff (not being a hard-core mathematician myself).

Analysis

The solution for any n is unique and well-known. The analysis goes like this:

Label the pegs as follows: the source peg is the one on which all the disks start; the destination peg is the one on which all disks are to end; the extra peg is none of the above.

Obviously the largest disk has to move. Fairly obviously, and easily proved, the optimal strategy is to move it directly from the source peg to the destination peg -- nothing is gained by moving it to the extra peg. In order to do this, none of the remaining n-1 disks can be on the source peg (or the largest disk couldn't be moved); nor can they be on the destination peg (or the largest disk couldn't go there). So they all must be stacked on the extra peg. Getting them there from the source peg is obviously exactly as difficult as getting them from there to the destination peg, which means the move in which the largest disk is moved is the middle move -- there are exactly as many moves before and after in an optimal solution. Note that the middle move, and the configuration of all disks at the start of the middle move, is forced.

But moving n-1 disks from the source peg to the extra peg is just the same thing as solving the (n-1)-disk Towers of Hanoi, except that you swap the identities of the extra and destination pegs. Likewise, moving n-1 disks from the extra peg to the destination peg is just the same thing as solving the (n-1)-disk Towers of Hanoi, except that you swap the identities of the source and extra pegs. So the only optimal way to solve the n disk problem is to: (1) solve the (n-1)-disk problem (2) move the n^th disk (3) solve the (n-1)-disk problem again. And the only way to do the first of these steps is to: (1) solve the (n-2)-disk problem (2) move the (n-1)^th disk (3) solve the (n-2)-disk problem again. And so on. Eventually the problem reduces to moving a 1-disk stack -- and we know how to do that! Everything else is, essentially, the middle move of some subproblem of the whole problem, which means every move of an optimal solution is forced, which means the optimal solution is unique. Moving 1 disk takes 1 move; moving 2 disks takes 2*1+1=3 moves; moving 3 disks takes 2*3+1=7 moves; and so on: moving n disks takes 2ⁿ-1 moves.

Configurations and game graph

In more generality, you can ask for the optimum solution to going from any valid disk configuration to any other. This is a much more difficult problem than the one discussed above (what I'll call the basic problem as opposed to the general problem), but it again is clear that at some point to move the largest disk (or rather, the largest disk that needs to be moved) from its source peg to its destination, all the smaller disks must be stacked onto the other peg.

So if you consider all the possible configurations for n disks, there must be 3 times as many as for n-1 disks, corresponding to each of the latter plus one of 3 possible positions for the largest disk. And to get from one of these three subsets of all configurations to another requires moving the largest disk -- and there's only one configuration from which that can be done.

Before going further let's define some compact notation for a configuration. A configuration of n disks can be represented as a sequence of n digits in the range 1-3 (or 0-2 if you're programming this in C!); the first digit identifies the peg the smallest disk is on, the second identifies the peg the second smallest disk is on, and so on. For example, the initial configuration of the 5-disk puzzle can be written 11111.

Now, we can picture the set of all configurations for the n-disk problem as follows. For the 1-disk puzzle there are 3 configurations: 1, 2, and 3. Any configuration can go to any other in one move. We can represent this by a triangle whose vertices correspond to the 3 configurations and whose edges represent valid single moves from one configuration to another:

Now for the 2-disk puzzle. As long as you don't move the second disk, the possible configurations are obviously the same as for the 1-disk puzzle. But the second disk can be on any of the three pegs. That means the 2-disk game graph consists of three copies of the 1-disk game graph, along with edges corresponding to moves in which the second disk goes from one peg to another. And as discussed above, there's only one configuration in which the second disk can go (for example) from the first peg to the second. So each of the three 1-disk game graphs links to each of the others by exactly one edge. The 2-disk game graph looks like this:

Likewise for the 3-disk puzzle: the game graph consists of three copies of the 2-disk game graph plus links between them; and since there is only one configuration from which the third disk can move from one given peg to another, there must be exactly one edge linking each 2-disk game graph to each of the others. The 3-disk graph looks like this:

Here are graphics of the game graphs for 1 to 6 disks. You can see larger versions on a separate page. Configuration labels are left to the reader as an exercise...

---

 n = 1  n = 2  n = 3  n = 4  n = 5  n = 6

---

This may be starting to look familiar to you. As n approaches infinity, the game graph becomes a closer and closer approximation to a Sierpinski triangle! It's rather surprising that there's such an intimate connection between the Towers of Hanoi and the Sierpinski triangle. This fractal turns up in lots of other places, too, often when you least expect it. In cellular automata, for instance.

Solving the basic Towers of Hanoi problem then becomes equivalent to asking for the shortest path on this graph from the top corner to one of the bottom corners. And the answer is obvious: Follow a straight path along the side of the triangle! That involves, of course, following a straight path along the side of one of the sub-triangles (say the red one), then taking the purple edge to the other sub-triangle (say the blue one), then following a straight path along the side of the blue sub-triangle. So it's easy to visualize how solving the n-disk problem amounts to solving the (n-1)-disk problem twice plus a single disk move.

The 4 peg problem

Analysis

Now suppose we have 4 pegs to work with, not 3. (This variant is sometimes called the Reve puzzle, and appeared in the first chapter of Henry Dudeney's Canterbury Puzzles.) Can we analyze this version of the puzzle the same way? No: immediately we run into a problem. Obviously the middle move of an optimal solution involves moving the largest disk from the source peg to the destination, and the remaining n-1 disks must be elsewhere. But whereas with 3 pegs there was only one possibility for "elsewhere", here there are 2 possibilities for each disk. That means that instead of having a unique configuration from which the middle move must occur, there are 2^n-1 such configurations! Not all of these will lead to optimal solutions, but it's not obvious which -- nor how many -- of them will.

You might impose the requirement that the configuration before the middle move be regular -- defined as follows: a configuration is regular if every disk that is on top of another disk is on top of the next larger disk. For example (generalizing the notation from the previous section), configuration 12234 is regular (disk 2 rests on disk 3) but configuration 12324 is not (disk 2 rests on disk 4). Then the configuration before the middle move must be: largest disk on source peg; destination peg empty; the k smallest disks on one extra peg, and the n-1-k remaining disks on the other extra peg. Then the algorithm to solve the puzzle is: (1) Move the first k disks to one extra peg (a 4-peg, k-disk problem) (2) move the next n-1-k disks to the other extra peg (a 3-peg, (n-1-k)-disk problem) (3) move the largest disk to the destination peg (4) move the (n-1-k) disks from the second extra peg to the destination peg (5) move the n disks from the first extra peg to the destination peg. If it takes M(n) moves to move n disks, then M(n) = 2((2^k-1)+M(n-1-k))+1, where 1 <= k <= n-1 is chosen to minimize M(n).

But such a constraint is not required by the rules of the puzzle. And in fact, not all optimal solutions satisfy the regularity constraint. On the other hand, no cases are known in which none of the optimal solutions obey the constraint. (This is the case for more than 4 pegs as well.) Perhaps it can be proved that at least one optimal solution for any n-disk, m-peg problem satisfies the regularity constraint. But no such proof is yet known.

(For more on the Reve puzzle and related variants, see Paul K. Stockmeyer, "Variations on the Four-Post Tower of Hanoi Puzzle", CONGRESSUS NUMERANTIUM 102 (1994), pp. 3-12. (Proceedings of the 25th Southeastern International Conference on Combinatorics, Graph Theory and Computing.))

Configurations and game graph

As before, we can think about visualizing the set of legal configurations for the n-disk, 4-peg puzzle. There are 4 subsets instead of 3 this time, corresponding to the (n-1)-disk configurations combined with each of 4 positions for the largest disk. This time, however, there generally is not just a single link from each subset to each other: there are 2^n-1 of them.

For the 1-disk puzzle the game graph can be represented by 4 points each linked to all 3 others; you can draw this in a plane but it's more naturally represented in 3-space as a tetrahedron. For 2 disks there are 4 tetrahedra. Each is linked to each of the others by two moves. For 3 disks there are 4 of the above polyhedra, each linked to each of the others by four moves. And so on.

Here are graphics of the game graphs for 1 to 6 disks. They're drawn as planar projections of 3-dimensional polyhedra. You can see larger versions on a separate page. Configuration labels are left to the reader as an exercise...

---

 n = 1  n = 2  n = 3  n = 4  n = 5  n = 6

---

Note that the 2-disk graph, if drawn with all edges equal in length, consists of a cuboctahedron with tetrahedral caps on 4 of the triangular faces. But for larger numbers of disks the links cannot be made all the same length.

Comparison of these pictures to the ones for the 3-peg puzzle makes it clear how much more complex the addition of a single peg makes it. To solve the basic 4-peg problem is to find the shortest path from the top vertex to one of the outermost bottom vertices. Unlike the 3-peg version, that path isn't obvious -- especially considering by "shortest" we mean smallest number of links, and some links must be drawn as longer than others.

In fact, you can probably see on the n=3 graph why the optimal solution is not analogous to the "straight along the edge" solution for the 3-peg problem. Not that there is a straight edge to follow anyway, but an approximation thereof might consist of going from (say) the top of the red sub-graph to its lower left corner, taking the purple edge from there to the blue sub-graph, and then continuing to the lower left corner of the blue sub-graph. But that obviously isn't optimal, because there's a "longer" purple path from the interior of the red sub-graph to the interior of the blue sub-graph. You can see at a glance that there are paths using that link that have fewer edges than any paths using the "short" purple edge.

More than 4 pegs

Masochist.

As before, if the regularity constraint is imposed, we can find optimal solutions for any number of disks and pegs. But again, there is no proof that such a constraint is required.

Presumably the game graph for the m-peg puzzle is most naturally drawn in m-1 dimensions, with the 1-disk graph consisting of a polytope with m vertices and m(m-1)/2 edges and the n-disk graph consisting of m (n-1)-disk polytopes connected by (m-2)^n-1 edges. Drawing such graphs is (wait for it...) left as an exercise.