The Analytical Tower 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.

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 2n − 1, where n is the number of discs. This result is obtained by noting that steps 1 and 3 take Tn − 1 time and step 2 takes constant time, giving Tn = 2Tn − 1 + 1.

Brain training and puzzle games are just one of the ways to help you stay in shape. Check our other games, if you have any question please let us know here: Contact