Towers of Hanoi

In the classic problem of the Towers of Hanoi, you have 3 towers and n disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom. You have the following constraints:

  1. Only one disk can be moved at a time.
  2. A disk is slid off the top of one tower onto another tower.
  3. A disk cannot be placed on top of a smaller disk.

Write a program to move the disks from the first tower to the last using stacks.

Solution

Let’s first discuss the base case. It is trivial to move one disk from the origin to the destination. For two disks, the procedure looks like so :

[1,2], [],    []
[2],   [],    [1]
[],    [2],   [1]
[],    [1,2], []

In order to move n disks from the origin to the destination, we need to move n-1 disks from the origin to the buffer, move disk n to the destination, and move disks {1 ... n-1} from the buffer to the destination.

The base case of our recursion is when n <= 0, in which case we terminate the recursion.

def move_disks(n, origin, destination, buffer):
  if(n <= 0):
    return

  move_disks(n-1, origin, buffer, destination)

  disk = origin.pop()
  destination.push(disk)

  move_disks(n-1, buffer, destination, origin)