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:
A prose version of the same algorithm follows:
You now have 2 disks stacked correctly on peg C, peg B is empty again
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 2n-1.
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.
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").