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:

1. move disk 1 to peg B
2. move disk 2 to peg C
3. 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

1. move disk 3 to peg B
2. 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ⁿ-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").