# The Tower of Hanoi - Myths and Maths

The *Tower of Hanoi* (TH) is a classic puzzle that was invented by *Éduard Lucas* (1842-1891) using the alias *N. Claus (de Siam)*, an anagram of *Lucas d'Amiens*. Given three pegs, two of them empty, and a pile of disks of decreasing size is stacked on the third one. The problem is to move the stack to another peg, moving one disk at a time from one peg to another, but never putting a larger disk on top of a smaller one (*the divine rule*). The *Chinese ring* puzzle (CR) and the topologically equivalent *Cardano rings* are related. In the latter two the problem is to get all the rings off the upper bar or to remove the string from the linked pillar structure. (See image below.) These puzzles are older and CR, which Lucas called *Baguenaudier* puzzle, has probably inspired him to formulate the TH puzzle.

So this is a book about recreational mathematics, but do not be mistaken, the origin of the questions may be recreational, the problems discussed are undeniable mathematics. There is a lot of graph theory, automata, group actions, complexity analysis and algorithmic aspects around with definitions, theorems and proofs.

Chapter 0 gives an introduction to the problem and the history of the TH puzzle and other related puzzles, but it also introduces definitions and properties of graphs that are used in solving these problems.

Then chapter 1 discusses the CR puzzle as a prototype to set up a model for approaching this kind of problems. The classical TH problem is then much more thoroughly discussed in chapter 2. Algorithms and proofs are given for optimal (w.r.t. the number of steps) solutions. The simplest problem is to move a perfect pile from one peg to another one following the divine rule. All possible intermediate states are called regular. It is more difficult to transform an arbitrary regular state into another one. To solve this, a good understanding and analysis of the associated graph becomes more important.

Lucas considered also another problem where the disks are placed randomly on the three pegs, and the goal is still to transform this irregular state to a perfect or regular state still following the divine rule. That's a short chapter 3.

The next chapter introduces another type of graphs to analyse the TH problem. They are called Sierpinski graphs because of their relation with the Sierpinski triangle.

Generalizing TH from 3 pegs to 4 or more pegs, still looking for an optimal solution (known as Reve's problem), goes way beyond a trivial step. So there is much intuition, conjectures and open problems to be found in chapter 5.

Some further variations are briefly discussed in the next 3 chapters. like more towers (of different color) and more pegs, and/or relaxing the rules of the game (chapter 6) or *Towers of London*: colored balls on a number of pegs to be brought form one state to another in a minimum number of steps (chapter 7) or with oriented disk moves (chapter 8).

Chapter 9 is just a list of open problems that were encountered in the previous chapters.

Chapters 0-8 are followed by a list of exercises (hints and solutions are provided in an appendix). In principle the mathematics needed are all introduced in the text, but the introduction to the necessary concepts is kept to a minimum and some basis is tacitly assumed known. For example, the notion of group is used without much ado. Hence a certain mathematical background and some familiarity with graphs is advisable and even required if you want to solve the exercises. Besides the usual subject and name indexes, the glossary of terms with one-liner definitions is quite useful to recall a concept of a previous chapter if you are not so familiar with graphs. The authors use a very pleasant and amusing style, but they keep the discussion to the point, and leave much more to be explored using many pointers to the extensive reference list. The many illustrations make the technicalities more easy to digest.

Thus if you love puzzles, and more in particular the mathematics behind it, this is a book for you. That holds for mathematicians but for computer scientists as well. Also if you are looking for a lifelasting occupation, then you may find here a list of open problems that will keep you busy for a while.

**Submitted by Adhemar Bultheel |

**23 / Feb / 2013