Games - Tower of Hanoi

Home > Listing Index > Games > Tower of Hanoi

	Games - 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 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 disks, 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.

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.

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 to the power n) − 1.

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 not involve moving the smallest disk again.

[ Visit the complete Wikipedia entry for Tower of Hanoi ]

Searches on eBay

tower of hanoi