Tower of Hanoi

A classic recursive problem in computer science

Story & Origin

The Tower of Hanoi game was invented by the French mathematician Édouard Lucas in 1883.

He created an accompanying legend: In a temple in Benares (India), there is a room containing 3 posts and 64 golden disks of different sizes. The monks here have been continuously moving these disks according to a strict rule since the beginning of the universe.

"It is believed that when the last monk completes moving all 64 disks to the new post, the world will end."

Why is it famous?

This is the classic and most perfect illustration of Recursion in programming and algorithms.

The minimum number of moves required to solve the puzzle with n disks is 2n - 1.

With 64 disks, it requires 264 - 1 moves.
If one disk is moved per second, it would take...
~ 585 billion years!
(About 42 times the age of the universe).

Rules of the Game

  • Only one disk may be moved at a time.
  • Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
  • Never place a larger disk on top of a smaller disk.
Goal: Move the entire stack from the leftmost peg to the rightmost peg.

Solving Strategy

To solve the problem, apply the principle of Recursion:

  1. Move the top n-1 disks from the Source peg to the Auxiliary peg.
  2. Move the largest disk (nth disk) to the Destination peg.
  3. Move the n-1 disks from the Auxiliary peg to the Destination peg.
Tip: For an odd number of disks, make your first move to the Destination peg. For an even number, make your first move to the Auxiliary peg.