• 0

Tower of hanoi

Problem :

The Towers of Hanoi is a classic puzzle with 3 pegs and multiple disks of different sizes.
The goal of the puzzle is to move all the disks from the first peg to the third peg according to the following rules :

  • Only one disk can be moved at a time.
  • You can only move the top disc in a stack.
  • No disk may be placed on top of a smaller disk.


  • Move a tower of height-1 to the buffer peg, using the destination peg.
  • Move the remaining disk to the destination peg.
  • Move the tower of height-1 from the buffer peg to the destination peg using the source peg.

To move n disks, the min number of required steps are 2^n - 1. For example, to move 3 disks the min number of steps are (2^3 - 1) = 7.

Watch the following video to understand the mathametics behind it from MIT!

Solution :

Visualization :


References :