Introduction
The Towers of Hanoi is a wellknown 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:
n=5 disks on first of three pegs: 
    _     ___     _____     _______     _________    
The task is to move all the disks to one of the other pegs, subject to two rules: (1) Only one disk may be moved at a time, from the top of the stack on one peg to the top of the stack on another, and (2) A larger disk may not be moved onto a smaller disk.
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 hardcore mathematics. Here I stick with some of the easier stuff (not being a hardcore mathematician myself).
Analysis
The solution for any n is unique and wellknown. 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 n1 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 n1 disks from the source peg to the extra peg is just the same thing as solving the (n1)disk Towers of Hanoi, except that you swap the identities of the extra and destination pegs. Likewise, moving n1 disks from the extra peg to the destination peg is just the same thing as solving the (n1)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 (n1)disk problem (2) move the n^{th} disk (3) solve the (n1)disk problem again. And the only way to do the first of these steps is to: (1) solve the (n2)disk problem (2) move the (n1)^{th} disk (3) solve the (n2)disk problem again. And so on. Eventually the problem reduces to moving a 1disk 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^{n}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 n1 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 13 (or 02 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 5disk puzzle can be written 11111.
Now, we can picture the set of all configurations for the ndisk problem as follows. For the 1disk 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:
Game graph for n=1 
1
/
/
23

This is the game graph for the 1disk puzzle.
Now for the 2disk puzzle. As long as you don’t move the second disk, the possible configurations are obviously the same as for the 1disk puzzle. But the second disk can be on any of the three pegs. That means the 2disk game graph consists of three copies of the 1disk 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 1disk game graphs links to each of the others by exactly one edge. The 2disk game graph looks like this:
Game graph for n=2 
11 / / 2131 / / 23 32 / / / / 33131222 
Here the three 1disk graphs are shown in red, blue, and green, and the links between them are in purple.
Likewise for the 3disk puzzle: the game graph consists of three copies of the 2disk 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 2disk game graph to each of the others. The 3disk graph looks like this:
Game graph for n=3 
111 / / 211311 / / 231 321 / / / / 331131121221 / / 332 223 / / / / 132232 323123 / / / / 122 212 313 133 / / / / / / / / 222322312112113213233333 
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…
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 subtriangles (say the red one), then taking the purple edge to the other subtriangle (say the blue one), then following a straight path along the side of the blue subtriangle. So it’s easy to visualize how solving the ndisk problem amounts to solving the (n1)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 n1 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^{n1} 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). 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 n1k 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 4peg, kdisk problem) (2) move the next n1k disks to the other extra peg (a 3peg, (n1k)disk problem) (3) move the largest disk to the destination peg (4) move the (n1k) 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) = 22^{k}1)+M(n1k?+1, where 1 <= k <= n1 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 ndisk, mpeg 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 FourPost Tower of Hanoi Puzzle” (Postscript file), CONGRESSUS NUMERANTIUM 102 (1994), pp. 312. (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 ndisk, 4peg puzzle. There are 4 subsets instead of 3 this time, corresponding to the (n1)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^{n1} of them.
For the 1disk 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 3space 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 3dimensional polyhedra. You can see larger versions on a separate page. Configuration labels are left to the reader as an exercise…
Note that the 2disk 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 3peg puzzle makes it clear how much more complex the addition of a single peg makes it. To solve the basic 4peg problem is to find the shortest path from the top vertex to one of the outermost bottom vertices. Unlike the 3peg 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 3peg 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 subgraph to its lower left corner, taking the purple edge from there to the blue subgraph, and then continuing to the lower left corner of the blue subgraph. But that obviously isn’t optimal, because there’s a “longer” purple path from the interior of the red subgraph to the interior of the blue subgraph. 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 mpeg puzzle is most naturally drawn in m1 dimensions, with the 1disk graph consisting of a polytope with m vertices and m(m1)/2 edges and the ndisk graph consisting of m (n1)disk polytopes connected by (m2)^{n1} edges. Drawing such graphs is (wait for it…) left as an exercise.
Graphics created using Rotater for the Macintosh