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 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.
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:
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 node coordinates 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. There are 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):
As we add the third disk, the game becomes noticeably less trivial. There are now many more "wrong" moves than there are "right" ones:
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 seven triangular areas, displaying the solution graphs for 3, 4, 5, 6, 7, 8 and 9 disks. The musical rules for the robots in each area are the same. However, each area's available instruments (timbres) are different, so the sound changes over time as the robots wander through the landscape.
The interested reader is encouraged to explore the deep, underlying similarity between the Towers 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.