Tower of Hanoi

The Tower of Hanoi (also called Towers of Hanoi) is a mathematical game or puzzle. It consists of three pegs, and a number of discs of different sizes which can slot onto any peg. The puzzle starts with the discs neatly stacked in order of size on one peg, smallest at the top, thus making a conical shape.

The object of the game is to move the entire stack to another peg, obeying the following rules:

• only one disc may be moved at a time
• a disc can only be placed onto a larger disc (it doesn't have to be the adjacent size, though: the smallest disc may sit directly on the largest disc)

Contents

1 Origins 2 Solution 2.1 Recursive algorithm 2.1.1 Explanation of the algorithm 2.2 Practical algorithm 2.3 Gray code solution 3 Applications 4 Four pegs and beyond 5 In popular fiction 6 External links

Origins

The puzzle was invented by the French mathematician Edouard Lucas in 1883. There is a legend about a Hindu temple whose priests were constantly engaged in moving a set of 64 discs according to the rules of the Tower of Hanoi puzzle. According to the legend, the world would end when the priests finished their work. The puzzle is therefore also known as the Tower of Brahma puzzle. It is not clear whether Lucas invented this legend or was inspired by it.

If the legend were true, and if the priests were able to move discs at a rate of 1 per second using the smallest number of moves, it would take the priests 2⁶⁴ - 1 seconds or roughly 585 billion years. The universe is currently about 13.7 billion years old.

Solution

Most toy versions of the puzzle have 8 discs. The game seems impossible to many novices, yet is solvable with a simple algorithm:

Recursive algorithm

• label the pegs A, B, C -- these labels may move at different steps
• let n be the total number of discs
• number the discs from 1 (smallest, topmost) to n (largest, bottommost)

To move n discs from peg A to peg B:

1. move n-1 discs from A to C. This leaves disc #n alone on peg A
2. move disc #n from A to B
3. move n-1 discs from C to B so they sit on disc #n

The above is a recursive algorithm: to carry out steps 1 and 3, apply the same algorithm again for n-1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial.

The Tower of Hanoi is a problem often used to teach beginning programming, in particular as an example of a simple recursive algorithm. It is also an example of an exponential time algorithm — for all but the smallest number of discs, it will take an impractically huge amount of time, even on the fastest computers in the world. There is no way to improve on this, because the minimum number of moves required to solve the puzzle is exponential in the number of discs.

Using recurrence relations, we can compute the exact number of moves that this solution requires, which is <math>2^n - 1<math>, where <math>n<math> is the number of discs. This result is obtained by noting that steps 1 and 3 take <math>T_{n-1}<math> time and step 2 takes constant time, giving <math>T_n = 2T_{n-1} + 1<math>.

Explanation of the algorithm

A more human-readable version of the same algorithm follows:

1. move disc 1 to peg B
2. move disc 2 to peg C
3. move disc 1 from B to C, so it sits on 2

You now have 2 discs stacked correctly on peg C, peg B is empty again

1. move disc 3 to peg B
2. repeat the first 3 steps above to move 1 & 2 to sit on top of 3

Each time you re-build the tower from disc i up to 1, move disc i+1 from peg A, the starting stack, and move the working tower again.

Practical algorithm

Alternately move disc 1 and one of the larger discs. If two of the larger discs are available, always move the smaller one onto the larger. When you move an odd-numbered disc, always move it one peg clockwise; when you move an even-numbered disc, always move it one peg counterclockwise.

An even easier way to remember this solution is to notice that the smallest disk gets every second move, and always moves in the same direction. In between smallest disk moves, there is only one legal move that does does not involve moving the smallest disk again.

In spite of the simplicity of the algorithms, the shortest way to solve the problem with n discs takes 2ⁿ-1 moves. It is not known in general how many moves are required to solve the puzzle when there are more than 3 pegs. Thus it is not practical by sequential advancement to determine the position on three pegs of a large set of disks after some arbitrary large number of advancements.

Disk positions may be determined more directly from the binary representation of the move number (base 2 with a digit for each disk) where sequences of 1's or 0's represent sequences of consecutive disks on the same peg, and wherever the digit changes, the next disk migrates one peg left or right (or wraps to the opposite end). The most significant digit represents the largest disk and a leading 0 helps interpret whether the largest disk migrates from the initial peg. Placing alternating 1 and 0 digits below the digits of the move number detects migration in one direction where this matches the digit of the move number at a digit change and in the other where it does not match. So move 00000000... places 8 greatest disks on the initial peg, move 11111111... places them on the final peg, and move 11011000... has the greatest two disks on the final peg, the next one on the initial peg, the next two in the middle, and the next three on the initial peg, regardless of how many additional digits there are representing smaller disks. One could thus easily compute the positions of disks in a set of eighty disks after some mole of advancements, if the margin were but large enough to contain it.

Gray code solution

The binary numeral system of Gray codes gives an alternative way of solving the puzzle. In the Gray system, numbers are expressed in a binary combination of 0s and 1s, but rather than being a standard positional numeral system, Gray code operates on the premise that each value differs from its predecessor by only one (and exactly one) bit changed. The number of bits present in Gray code is important, and leading zeros are not optional, unlike in positional systems.

If one counts in Gray code of a bit size equal to the number of discs in a particular Tower of Hanoi, begins at zero, and counts up, then the bit changed each move corresponds to the disc to move, where the least-significant-bit is the smallest disc and the most-significant-bit is the largest.

This technique tells you which disc to move, but not where to move it to. Luckily, there is a rule which does. Simply, even-numbered discs should always be placed on either an odd-numbered disc or an empty peg, and odd-numbered discs should always be placed on either an even-numbered disc or an empty peg. If this rule is followed there should never be any ambiguity with where to place the disc. [1] (http://occawlonline.pearsoned.com/bookbind/pubbooks/miller2_awl/chapter4/essay1/deluxe-content.html#tower)

Applications

The Tower of Hanoi is frequently used in psychological research on problem solving. There also exists a variant of this task called Tower of London for neuropsychological diagnosis and treatment of executive functions.

As mentioned above, the Tower of Hanoi is popular for teaching recursive algorithms to beginning programming students. A pictorial version of this puzzle is programmed into the emacs editor, accessed by typing M-x hanoi. You can also find a sample algorithm written in Prolog.

Four pegs and beyond

Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four or more pegs is still an open problem. This is a good example of how a simple, solvable problem can be made dramatically more difficult by slightly loosening one of the problem constraints.

Though it is not known exactly how many moves must be made, there are some asymptotic results. There is also a "presumed-optimal solution" that can be recursively applied to find a solution - see Paul Stockmeyer's survey paper (http://www.cs.wm.edu/~pkstoc/boca.ps) for an explanation and some variants of the four-peg problem.

Although it agrees with computer experiments for small numbers of discs, there is not yet a general proof that this presumed-optimal solution is in fact optimal. However, results in 2004 (http://epubs.siam.org/sam-bin/dbq/article/43101) showed that the presumed-optimal solution must be of the same order of magnitude as the optimal solution.

In popular fiction

In the classic science fiction story Now Inhale, by Eric Frank Russell (Astounding Science Fiction April 1939, and in various anthologies), the human hero is a prisoner on a planet where the local custom is to make the prisoner play a game until it is won or lost, and then execution is immediate. The hero is told the game can be one of his own species', as long as it can be played in his cell with simple equipment strictly according to rules which are written down before play and cannot change after play starts, and it has a finite endpoint. The game and execution are televised planet-wide, and watching the desperate prisoner try to spin the game out as long as possible is very popular entertainment; the record is sixteen days. The hero knows a rescue ship might take a year or more to arrive, so chooses to play Towers of Hanoi with 64 disks until rescue arrives. When the locals realize they've been had, they are angry, but under their own rules there is nothing they can do about it. They do change the rules that will apply to any future prisoners.

External links

• Theory, recursive and a per step algorithms with Java implementation (http://www.cut-the-knot.org/Curriculum/Combinatorics/TowerOfHanoi.shtml)
• Bicolor Tower of Hanoi (http://www.cut-the-knot.org/Curriculum/Combinatorics/BiColorTowerOfHanoi.shtml)
• Tower of Hanoi Facts (http://www.lawrencehallofscience.org/Java/Tower/towerhistory.html)
• Hanoimania, over 100 implementations of the Tower of Hanoi problem (http://www.kernelthread.com/hanoi/)
• Towers of Hanoi Online game (http://math.bu.edu/DYSYS/applets/hanoi.html)
• Play Towers of Hanoi Online (http://www.farfarfar.com/games/towers_of_hanoi/)
• Binary Numbers and the Standard Gray Code, with a discussion of the Gray Code solution (http://occawlonline.pearsoned.com/bookbind/pubbooks/miller2_awl/chapter4/essay1/deluxe-content.html#tower)de:Türme von Hanoi

eo:Turoj de Hanojo fr:Tours de Hanoï it:Torre di Hanoi he:מגדלי האנוי nl:Torens van Hanoi ja:ハノイの塔 sv:Tornen i Hanoi vi:Tháp Hà Nội