Towers of Hanoi

ny discussion of beauty in programming must necessarily begin with recursion in general, and the Towers of Hanoi in particular. This will be review for anyone who’s studied computer science, but that’s okay since I won’t have many readers at this point anyway.

The Towers of Hanoi is a puzzle of simple construction but fascinating complexity. It consists of three pegs. To start with, on one of the pegs is a number of disks, stacked from largest to smallest. The object is to move the stack of disks to one of the other pegs, with the restrictions that you can only move one disk at a time, and a disk may never be placed on a disk that’s smaller than it.

There’s a beautiful computer algorithm to solve it, and that I want to talk about. But the Towers of Hanoi was a toy long before there were computers. So first, have a play at solving it by yourself. Increase the number of disks if you find it too easy to start with. Most people, when they first start playing with it, end up moving disks pretty much randomly at the start. After a point you may find yourself making small goals, like “Okay, I need to get these smallest three disks over to this peg, so I can move the next biggest disk…” Eventually you realize that, if you’re starting with, say, six disks, you’re going to have to move five of them out of the way (onto the extra peg), then move the sixth and largest disk to the target peg, then move the first five on top of it.

So let’s look at the actual program that solves it. The number of disks has been made a parameter so we can eventually solve it for any number of disks. I’ll add comments to make it exceedingly clear what’s going on.

 private static void hanoi( int numberOfPegs, String fromPeg,
   String targetPeg, String otherPeg )
 {
  // First, move all but the largest disk to the extra peg.
  if (numberOfPegs > 1)
  {
   hanoi( /* move */ numberOfPegs-1, /* pegs */
   /* from the */ fromPeg,
   /* to the */ otherPeg,
   /* via the */ targetPeg);
  }

  // Next, move the largest disk to the target page. We'll just print 
  // out the move we're making.
  System.out.println("Move a disk from " + fromPeg + " to " + targetPeg);

  // Lastly, move the disks that we moved out of the way on top of 
  // the largest disk.
  if (numberOfPegs > 1)
  {
   hanoi( /* move */ numberOfPegs-1, /* pegs */
   /* from the */ otherPeg,
   /* to the */ targetPeg,
   /* via the */ fromPeg);
  }
 }

We’ve had to add the extra peg as the last parameter, just to keep track of it. But notice how similar it is to the original plan, of moving all but the largest disk out of the way, then moving the largest disk, then moving all the remaining disks on top of it. But as an algorithm it looks like it only sketches the broad plan. It just doesn’t look complex enough to solve that first step — moving all but the largest disk out of the way — not to mention he third step, which is just as complex. But miraculously, it works! Try running the code yourself. How could it possibly do all those intermediate steps?

It turns out that the problem of how to move n-1 disks from the “from” peg to the “other” peg is just a smaller, simpler version of the problem of moving n disks from the “from” peg to the “target” peg. It’s just that we’re now using the “extra” peg as our target peg, and the target peg as the extra peg. So this method will just be solving the problem for smaller and smaller versions of the problem, until eventually it has to solve it for only a single disk. And if you trace the code for what happens when there’s a single disk (when numberOfPegs==1), you’ll see that all it will do is the print statement.

To me, the Towers of Hanoi problem is the most beautiful algorithm there is. And it fits the requirements for a recursive algorithm perfectly; it can be broken up into smaller problems, until it reaches an exceedingly simple case (just moving a single disk).

I wonder how long it took after the first computers were made until the Towers of Hanoi was successfully programmed. Very probably it was done in machine code, using a stack of some sort. But what was the first language that would have allowed it to be done with a nice readable recursive function? I would love to have been a fly on the wall.

There’s lots more to the Towers of Hanoi, which I will cover in a later post.