# Introduction

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

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

- Only one disk may be moved at a time.
- Each move consists of taking the upper disk from one of the pegs
and sliding it onto another peg, on top of the other disks that may
already be present on that peg.
- No disk may be placed on top of a smaller disk.

## Explanation of the algorithm

A prose version of the same algorithm follows:

- move disk 1 to peg B
- move disk 2 to peg C
- move disk 1 from B to C, so it sits on 2

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

- move disk 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 disk *i* up to 1, move
disk *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.

## Applications

The Tower of Hanoi is frequently used in psychological research on problem solving. The Tower of
Hanoi is also used as a memory test by neuropsychologists trying to
evaluate amnesia. 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 popular for teaching
recursive algorithms to beginning programming students. The Tower of
Hanoi is also used as Backup rotation scheme when
performing computer data Backups where multiple tapes/media are involved.

## Four or more pegs

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.

This text is variously sourced from http://en.wikipedia.org/wiki/Towers_of_Hanoi (the Wikipedia entry for "Tower of Hanoi").