Tower of Hanoi

A model set of the Towers of Hanoi

The Tower of Hanoi or Towers of Hanoi is a mathematical game or puzzle. It consists of three pegs, and a number of discs of different sizes which can slide 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
no disc may be placed on top of a smaller disc

Origins

The puzzle was invented by the French mathematician Edouard Lucas in 1883. There is a legend about an Indian temple which contains a large room with three time-worn posts in it surrounded by 64 golden discs. The priests of Brahma, acting out the command of an ancient prophecy, have been moving these discs, in accordance with the rules of the puzzle. According to the legend, when the last move of the puzzle is completed, the world will end. 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 them 2⁶⁴ − 1 seconds or roughly 585 billion years. The universe is currently about 13.7 billion years old.

There are many variations on this legend. For instance, in some tellings, the temple is a monastery and the priests are monks. The temple or monastery may be said to be in different parts of the world - including Hanoi, Vietnam, and may be associated with any religion. In some versions, other elements are introduced, such as the fact that the tower was created at the beginning of the world, or that the priests or monks may make only one move per day.

Buddhists do build pagodas (a type of temple), some of these obey the rules of "Towers of Hanoi". The name "Towers of Hanoi" may have stuck from the time Indochina became exposed to the western world (e.g. occupied by the French).

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:

move n−1 discs from A to C. This leaves disc #n alone on peg A
move disc #n from A to B
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 $2^{n}-1$ , where $n$ is the number of discs. This result is obtained by noting that steps 1 and 3 take $T_{n-1}$ time and step 2 takes constant time, giving $T_{n}=2T_{n-1}+1$ .

A simple and elegant implementation in Haskell (a recursive, functional programming language) is as follows:

hanoi n = hanoi' n 1 2 3
hanoi' 0 _ _ _ = []
hanoi' n f i t = (hanoi' (n-1) f t i) ++ (f, t) : (hanoi' (n-1) i f t)

where n is the number of discs; this program returns a list of all the moves required.

Here is an mirrored implementation in SML programming language:

fun hanoi (0,_,_,_) = [] | 
hanoi (n,l,c,r) = 
  hanoi(n-1,l,r,c) @ (l,c)::hanoi(n-1,r,c,l);

Explanation of the algorithm

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

move disc 1 to peg B
move disc 2 to peg C
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

move disc 3 to peg B
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.

Therefore, We can observe and say that number of moves required to move n number of plates will be $2^{n}-1$ .

Practical algorithm

(Above) Solution for 3 discs. (Below) Solution for 4 discs.

Refresh the page while in this section to see the similarities between the two solutions.

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 if the number of total discs is even or counterclockwise if the number of total discs is odd; when you move an even-numbered disc, always move it in the opposite direction as the odd-numbered discs.

An even easier way to remember this solution is to notice that the smallest disc gets every second move, and always moves in the same direction. In between smallest disc moves, there is only one legal move that does not involve moving the smallest disc again. For an odd number of discs, move the smallest disc to the left. For an even number of discs, move the smallest disc to the right.

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 discs after some arbitrary large number of advancements.

Binary solutions

Disc positions may be determined more directly from the binary (base 2) representation of the move number (the initial state being move #0, with all digits 0, and the final state being #2ⁿ−1, with all digits 1), using the following rules:

There is one binary digit (bit) for each disc
The most significant (leftmost) bit represents the largest disc. A value of 0 indicates that the largest disc is on the initial peg, while a 1 indicates that it's on the final peg.
The bitstring is read from left to right, and each bit can be used to determine the location of the corresponding disc.
A bit with the same value as the previous one means that the corresponding disc is stacked on top the previous disc on the same peg.
- (That is to say: a straight sequence of 1's or 0's means that the corresponding discs are all on the same peg).
A bit with a different value to the previous one means that the corresponding disc is one position to the left or right of the previous one. Whether it is left or right is determined by this rule:
- If this is an odd-numbered disc, counting from the largest disc or most-significant bit (e.g. the largest disc, the third-largest, fifth-largest, etc), a 1 moves it one peg to the left, and a 0 moves it one peg to the right.
- If this is an even-numbered disc, counting from the largest disc or most-significant bit (e.g. the second-largest disc, the fourth-largest, sixth-largest, etc), a 1 moves it one peg to the right, and a 0 moves it one peg to the left.
- This assumes that the initial peg is on the left and the final peg is on the right.
- It also assumes "wrapping" - so the right peg counts as one peg "left" of the left peg, and vice versa.

For example, in an 8-disc Hanoi:

Move #0 (00000000)
- The largest disc is 0, so it is on the left (initial) peg.
- All other discs are 0 as well, so they are stacked on top of it. Hence all discs are on the initial peg.
Move #255 (11111111)
- The largest disc is 1, so it is on the right (final) peg.
- All other discs are 1 as well, so they are stacked on top of it. Hence all discs are on the final peg and the puzzle is complete.
Move #216 (11011000)
- The largest disc is 1, so it is on the right (final) peg.
- Disc two is also 1, so it is stacked on top of it, on the right peg.
- Disc three is 0, so it is on another peg. Since it is odd-numbered, a 0 moves it one peg to the right. Therefore it is on the left (initial) peg.
- Disc four is 1, so it is on another peg. Since it is even-numbered, a 1 moves it one peg to the right. Therefore it is on the middle peg.
- Disc five is also 1, so it is stacked on top of it, on the middle peg.
- Disc six is 0, so it is on another peg. Since it is even-numbered, a 0 moves it one peg to the left. Therefore it is on the left (initial) peg.
- Discs seven and eight are also 0, so they are stacked on top of it, on the left (initial) peg.

One could thus easily compute the positions of discs in a set of eighty discs after some mole of advancements, if the margin were but large enough to contain it.

The source and destination pegs for the nth move can also be found elegantly from the binary representation of n using bitwise operations. To use the syntax of the C programming language, the nth move is from peg (n&n-1)%3 to peg ((n|n-1)+1)%3, where the discs begin on peg 0 and finish on peg 1 or 2 according as whether the number of discs is even or odd. This permits a very fast nonrecursive computer implementation of the solution.

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, a disc should never be placed on another disc of the same parity (i.e. even discs should not be placed on even discs, nor odd on odd). If this rule is followed there should never be any ambiguity with where to place the disc. [1]

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.

The Tower of Hanoi is also used as Backup rotation scheme when performing computer data Backups where multiple tapes/media are involved.

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. There is also a sample algorithm written in Prolog.

The Tower of Hanoi is also used as a memory test by neuropsychologists trying to evaluate amnesia.

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 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 showed that the presumed-optimal solution must be of the same order of magnitude as the optimal solution.

Description of the presumed-optimal solution

The problem for four pegs is sometimes called "Reve's puzzle". A solution for four (or more) pegs, which has not been proved to be optimal, is described below:

Let $n$ be the number of discs.
Let $r$ be the number of pegs.
Define $T(n,r)$ to be the number of moves required to transfer n discs using r pegs

The algorithm can be described recursively:

For some $k$ , $1\leq k<n$ , transfer the top $k$ discs to a single other peg, taking $T(k,r)$ moves.
Without disturbing the peg that now contains the top $k$ discs, transfer the remaining $n-k$ discs to the destination peg, using only the remaining $r-1$ pegs, taking $T(n-k,r-1)$ moves.
Finally, transfer the top $k$ discs to the destination peg, taking $T(k,r)$ moves.

The entire process takes $2T(k,r)+T(n-k,r-1)$ moves. Therefore, we should pick $k$ for which this quantity is minimum.
This algorithm (with the above choice for $k$ ) is presumed to be optimal, and no counterexamples are known.

In popular culture

In the classic science fiction story Now Inhale, by Eric Frank Russell (Astounding Science Fiction April 1959, 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 discs 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, which will apply to any future prisoners. This story makes reference to the legend about the Buddhist monks playing the game until the end of the world, and refers to the game as arkymalarky. (The slang term "malarky", meaning nonsense, pre-dates this story by at least 30 years. [2])

In the Doctor Who serial "The Celestial Toymaker", the Toymaker challenges the Doctor to complete the "Trilogic Game" (eight disc Hanoi) in exactly 1,023 (2¹⁰ − 1) moves. Apparently, both the Doctor and the Toymaker were unaware of the algorithm above.

There is a band named Towers of Hanoi.

In video games

The puzzle is featured regularly in adventure and puzzle games. Since it is easy to implement, and easily-recognised, it is well-suited to use as a puzzle in a larger graphical game. Some implementations use straight discs, but others disguise the puzzle in some other form. What follows is a partial list of games which use the puzzle:

External links

Online Demonstration

History

Algorithm

Events

[3] Workshop on the Tower of Hanoi and Related Problems, 18.9. - 22.9.2005, Maribor, Slovenia

Template:Link FA