Wednesday, March 7, 2007

Towers of Hanoi

The Towers of Hanoi puzzle is not that easy to solve. If you want to play a digital version of that puzzle, go to Towers of Hanoi DHTML game.

Now let's see how to solve a four disk puzzle.



This is the start position.



And this is the end position.

A step in between the start and end position could be something like this:



Directly followed by this:



This is the only move the largest red disk will make.

How about the next disk, the yellow one?

Well, it has three positions, the start position, on tower 2 (while the red disk is still on tower 1), and on top of the red disk on tower 3):



The red disk hasn't moved yet, and the yellow disk have moved to tower 2.



The red disk has moved, and the yellow disk has moved on top of the red disk on tower 3.

Now, let's recap what we've done so far:

  • We have moved the disks on top of the red disk, to make the red disk free, and move it to it's final tower.
  • In order to make the red disk free to move from tower 1 to tower 3, we have to move the other disks to tower 2, with the yellow disk at the bottom of the pile of disks. In order to be able to move the yellow disk to tower 2, we need to move the disks on top of it to tower 3. Then we move the yellow disk to tower 2, and the other disks on top of the yellow disk on tower 2.
  • Once the red disk is on tower 3, we need to move the yellow disk on tower 2 to tower 3. In order to do that, we need to move the disks on top of the yellow disk to tower 1. After that, we can move the yellow disk on top of the red disk on tower 3.

I see a pattern there, in order to move a disk at the bottom of a pile of disks, we need to move the disks on top of it to the spare tower. If you want to move a disk from tower O to tower D, the remaining tower S is the spare tower (where O, D, and S can either be one of 1, 2, 3). That smells like a recursive process.

So this is the process:

  • move disks on top of red disk to tower 2:
    • move disks on top of yellow disk to tower 3:
      • move cyan disk on top of green disk to tower 2
      • move green disk to tower 3
      • move cyan disk to tower 3, on top of green disk
    • move yellow disk to tower 2
    • move disks on tower 3 to tower 2, on top of yellow disk:
      • move cyan disk on top of green disk to tower 1, on top of red disk
      • move green disk to tower 2, on top of yellow disk
      • move cyan disk to tower 2, on top of green disk
  • move red disk to tower 3
  • move disks on tower 2 to tower 3, on top of red disk:
    • move disks on top of yellow disk to tower 1:
      • move cyan disk on top of green disk to tower 3
      • move green disk to tower 1
      • move cyan disk to tower 1, on top of green disk
    • move yellow disk top tower 3, on top of red disk
    • move disks on tower 1 to tower 3, on top of yellow disk:
      • move cyan disk on top of green disk to tower 2
      • move green disk to tower 3, on top of yellow disk
      • move cyan disk to tower 3, on top of green disk

Here is an animation of this procedure:



If we study this more closely, we can see that in order to move a pile of disks from the origin to the destination, you need to:

  1. park the disks on top of the bottom disk to the spare
  2. move the freed bottom disk to it's destination
  3. move the parked pile back on the bottom disk

That should be enough to understand the puzzle, but not quite enough to develop our program to solve the puzzle.

No comments: