Towers of Hanoi

One of the most famous recursive problems.

Table of contents
  1. Gist of the problem
  2. Recursive solution
    1. Base case
    2. Inductive step
  3. Pseudocode

Gist of the problem

There are three pegs (source, goal, auxiliary), and $n$ disks of different sizes.

The disks are initially sorted on the source peg, with the largest disk at the bottom.

The goal is to move all the disks to the target peg, in the same sorted order.

You can only move one disk at a time (the one on the top of a peg), and you cannot place a larger disk on top of a smaller disk.

Recursive solution

Base case

When there is one disk, move it from the source peg to the target peg.

Inductive step

Note our base case for a single disk. We can move the single disk from the source peg to the target peg.

It is important to note that a solution is not limited to just moving the disk from the source peg to the target peg. It is a solution that can be used to move the disk from one peg to another peg (given the help of the auxiliary peg).

Now what if there was actually a larger second disk at the bottom of the source peg?

Since this is the largest disk, it does not invalidate our previous solution.

We can still use our solution for the single disk, so that one disk is now on the auxiliary peg.

Then, we can move the second disk (the largest disk) from the source peg to the target peg.

It is important to understand that once you’ve moved the current largest disk to the target peg, it essentially disappears from the problem as if it was never there in the first place.

Now we have a single disk on the auxiliary peg, which means we can use our base case solution to move the disk to the target peg.

Then we have solved the problem for two disks.

There exists a way to move the two disks from one peg to another peg in the same sorted order.

What if there was actually a third disk at the bottom of the initial source peg?

For the top two disks, we can use the previous solution to move them to the auxiliary peg.

Then we move the third disk (largest disk) from the source peg to the target peg.

Since the largest disk is on the target peg, it disappears from the problem.

Now we have two disks on the auxiliary peg, we can use the previous solution to move them to the target peg.

Then we have solved the problem for three disks.

With $n$ disks, the same thing happens.

We move the top $n-1$ disks to the auxiliary peg, using a previous solution.

We move the largest disk left on the source peg to the target peg.

Then this target peg disappears from the problem.

We can move the $n-1$ disks from the auxiliary peg to the target peg, because we’re back to our previous case of $n-1$ disks.

Pseudocode

def move_disk(from, to):
  print "Move disk from " + from + " to " + to

def towers_of_hanoi(n, source, target, aux):
  if n < 0:
    return
  if n == 1:
    return move_disk(source, target)
  towers_of_hanoi(n - 1, source, aux, target)
  move_disk(source, target)
  towers_of_hanoi(n - 1, aux, target, source)