Monday, June 23, 2008

Towers of Hanoi

A while ago I noticed that Adobe was offering a free 30-day trial of some of their multimedia authoring products. I had played around with Flash several years ago, so I decided to see if the new CS3 version had anything new. It was completely different, and it took me all 30 days to figure it out to the point where I could create a simple application, which I offer here for your puzzling pleasure. (You need the Flash Player for it to work, which is free to download at the link above).

This is a common problem in beginning programming classes, which is where I came across it. The challenge is to move all the disks from the left tower to the right tower, using the center tower as needed for a holding spot. There are only two rules: (1) you can move just one disk at a time; and (2) you can never place a larger disk on top of a smaller one. I recommend starting with 3 or 4 disks until you get the hang of it.

Theoretically there is no limit to how many disks could be transferred in this way, but the number of moves required grows exponentially. The puzzle takes its name from the legend of a Vietnamese monastery where the monks work in shifts to move 64 disks from the original tower to the final one. When they complete the puzzle, the world will end. But even if they were to make one move per second, and used the most efficient method, it would take them about 600 billion years to finish. That's about 50 times the current age of the universe. Astronomers estimate our sun will flare into a red giant in about 5-6 billion years, swallowing the earth in flame. So we've got bigger problems than the Towers of Hanoi. That's the power of exponential growth (the same principle behind compound interest).

Leave a comment if you're able to complete the puzzle for 6 or more disks. If you are stumped and want some help, leave a comment or shoot me an email. If you try it with 10 disks, the top disk is so small it's hard to see--sorry about that. I would have fixed it if I hadn't run out of time. I'd like to buy Flash, but the price tag is too steep for now.


Lincolnlogger said...

I did 6, I'd need more time to complete more. finished in less than 10 minutes though.

Michelle said...

I did 6. I seem to remember there being some connection with binary numbers, but I can't recreate it. In any case, there is a definite pattern to solve it, it's just all subsets of the smaller disk cases (move the top n-1 disks to the middle, then move the nth over, and undo the moves to put the n-1 disks on top).

DTR said...

That's right, Michelle. That explains why the number of moves essentially doubles for each additional disk. The shortest possible sequence for moving n disks involves (2^n)-1 moves. Moving ten disks requires at least 1023 moves. Six disks can be moved in 63 moves.