Explorations in 4-Peg Tower of Hanoi
2D and 3D visualizations of state transition graphs

Ben Houston
Exocortex Technologies
Hassan Masum
Carleton University


2D State Transitions Graphs

For 3-peg Tower of Hanoi, the state transition graph is familiar to many (see the three diagrams immediately below.) For larger and larger numbers of discs, these graphs are better and better approximations to the Sierpinski Gasket triangular fractal; see [Bogomolny] for an explanation of why this occurs. Analysis of these approximation graphs and some inferences for the properties of the Sierpinski Gasket are in [Hinz and Schief 1990].
 

However, the corresponding graph for 4-peg Tower of Hanoi is not obvious, and so we experimented with several different layouts. It is of interest to try to and a layout for 4-peg Tower of Hanoi which shows some of the patterns of the state transition graph in an understandable way. These graphs have interesting regularities which may aid in analysis.

In the series of figures below, we have a layout of the state space of the T(4,2), T(4,3), T(4,4) and T(4,5) problems - where T( p, d ) is the Tower of Hanoi problem with p pegs and d discs. One can see the many symmetries, and repeated sub-problem structure at various scales:
 


4 Pegs, 2 Discs


4 Pegs, 3 Discs


4 Pegs, 4 Discs


4 Pegs, 5 Discs

3D State Transition Graphs

Is there a natural 3-dimensional representation generated by the state transition graph for 4-peg Tower of Hanoi? The representations are not just finite approximations to the "Sierpinski Tetrahedron" in 3-space as one might first guess, as the graph contains many more edges. Not much is known yet about this graph, aside from basic information about the number of edges [Klavzar 1998], and the fact that it is non-planar for 3 or more discs [Hinz and Parisse 2002].

One way to generate such a 3D representation is to lay out the state transition graph in 3D space, and use a force layout method: nodes repel each other and change position until a stable state is reached where forces are in balance. This stable state is the graphical depiction. We have made the following videos demonstrating this pragmatic approach to graph layout:
 

 

For more information please see:

Ben Houston and Hassan Masum.  "Explorations in 4-peg Tower of Hanoi."  Carleton University Technical Report TR-04-10, November 2004.