Towers of Hanoi

Technical Background


The mathematical puzzle Les Tours de Hanoï was invented by the French mathematician Édouard Lucas (1842-1891), and first described in his 1883 publication Récréations Mathématiques. The premise is simple. Three pegs are attached upright to a horizontal board. Several disks of different sizes, with holes drilled through their centers, are stacked on one of the pegs, from smallest at the top to largest at the bottom. The object is to move all of the disks from one peg to another in as few moves as possible. There are three rules: 1) only one disk may be moved at a time; 2) a larger disk may never be placed atop a smaller disk; 3) each move must be complete and non-overlapping, that is, a disk removed from one peg must be moved to another peg before another disk may be moved.

Wooden Tower of Hanoi game

The solution to the puzzle can be represented as a graph, or map. For the trivial case where there is only one disk, the graph is a simple triangle in which each vertex represents the single disk positioned at one of the three pegs:

Solution map for one disk

The next level of the game, with two disks, is almost as trivial, but there are more possible moves, and the graph is correspondingly larger. Each node in the graph represents a unique positioning of the two disks amongst the three pegs; thus the coordinates of the node serve as a unique ID. Note that the map is symmetrical, and can be used to chart a solution starting from any of the three pegs, moving towards either of the other two. Thus there are actually six solutions to the puzzle, which are the sequences of moves (in both directions) along the straight lines between the vertices marked (1,1), (2,2) and (3,3):

Solution map for two disks

As we add a third disk, the game starts to become noticably less trivial. There are now many more "wrong" moves than there are "right" ones:

Position map for three disks

In fact, every time we add a disk, the number of nodes in the graph increases by a factor of three. The graph is self-similar: it contains copies of itself at different scales. For example, the graph for two disks consists of three copies of the graph for one disk, and the graph for three disks consists of three copies of the graph for two disks.

The size of the graph grows rather quickly as disks are added. For N disks there are 3N nodes, so by the time we get to ten disks there are 59049 nodes, or unique positions of the disks among the three pegs. Each side of the outermost triangle is 2N nodes in length, so for the 10-disk game the solution requires 1024 - 1 = 1023 moves.

The visual design for Towers of Hanoi divides the screen into 7 triangular areas, in which are displayed the solution graphs for 3, 4, 5, 6, 7, 8 and 9 disks. The musical rules for the robots in each area are basically the same, although the collection of available instruments (timbres) in each area is different, so that the sound changes over time as the robots wander through the landscape.

Towers of Hanoi screen areas

The interested reader is encouraged to explore the deep, underlying similarity between the Tower of Hanoi puzzle and two other mathematical structures: the Sierpiński gasket and Pascal's triangle, both of which have been widely discussed on the internet and in the mathematical literature.



Back to Towers of Hanoi


Copyright © 2014 Signals and Noises
All rights reserved worldwide.