Save this page as your homepage!

### Brain Stretching - Training of Tower of Hanoi

Now you can try some brain strechting and training by playing the Tower of Hanoi or Towers of Hanoi, which is a mathematical game/ 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 beginners, 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) to n (largest)

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.

Recommend This Page To A Friend!

The Tower of Hanoi is a problem often used brain stretching games, also for 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. A very nice game ideal for brain training.

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.

Recommend This Page To A Friend!

**Salim ©
2007 BrainMetrix.com All Rights Reserved**