So, right off, go play this simple game. (You might need Flash). Try it with a few different numbers of disks. If you get frustrated or (rightfully) don’t have the patience for the higher-disk puzzles, the same site offers this solver. This is the Tower of Hanoi puzzle, a famous riddle of sorts introduced by Edouard Lucas in the late 19th century. Solving the puzzle is somewhat trivial, (once you get the trick of it), but its properties continue to interest people today, and it comes with a bit of lore to boot.
This is part two of my backward crawl through time, showing you that the ideas of computation and complexity exist outside of those gadgets and devices you hold in your hand. This is a broad topic, so I’m sticking to a theme, namely powers of two. Powers of two, or exponential growth, is something you are probably already familiar with, as the explosive nature of changing an exponent is at the heart of all the joy we get out of Moore’s law. Last week I showed you that the game of 20 questions is actually a game of a million questions if you were to try to plan your questions perfectly. As you may have already noticed, working through the Tower of Hanoi quickly becomes just as tedious.
The Tower of Hanoi is relevant historically for a few reasons. The puzzle itself is not an important mathematical problem, but it came with a neat feature: You could scale up the number of disks to get a new, more complicated puzzle. This reveals a second, more interesting puzzle underneath: Surely you can solve a 3-disk puzzle and a 4-disk puzzle and a 5-disk puzzle and so-on, but can you solve an n-disk puzzle? That is, can you describe a solution that works no matter how many disks there are? Being from the late 19th century, this puzzle predates any real notion of algorithm, and yet an algorithm it demands. This is why the puzzle was so evocative for its time; it was asking people to dream up a computer program.
The wikipedia page on the puzzle can walk you through several of these generic solutions if you are interested (it also relates these generic solutions to fractals, but that’s extra credit material at this point). Note that while these solutions are conceptually simple, actually slogging through moving the pieces gets very tiresome when you have a lot of disks; the solutions say nothing of how many moves it takes to get to the end.
If we work through the recursive solution, we can see what happens. Let’s start with one disk. The puzzle is trvial in this case; you just move the disk to the right tower (one move). For two disks, you must uncover the bottom disk, so you move the top disk to the middle, (this is enacting the solution to the 1-disk case; one move), move the bottom disk to the right (one move) and move the top disk to the right (one move; three total). For three disks, again you need to uncover the bottom disk, so you move the top two disks to the middle (use the 2-disk solution to do this; three moves), move the bottom disk (one move) and move the bottom two disks to the right (three moves; seven total). This generic solution is recursive because for any value of n, you can explain what to do by saying “move the top n-1 pieces to the middle; the bottom piece to the right, and the remaining n-1 to the right.” In other words, you use the very solution you are trying to describe as a step in your solution. Because each n uses the n-1 solution twice, you can see that that number of moves needed about doubles each time you add a new disk to the puzzle: 1,3,7,15,31,etc. Each number one less than a power of two.
And so we have come back to those powers of two that excite us so much. It would seem that this doubling was exciting back when this puzzle was first introduced as well, because the puzzle came with a legend attached. While the legend is obviously apocryphal, it speaks to how fascinating the explosive nature of exponents can be. The legend says that there is a temple with a 64-disk Tower of Hanoi, and monks tirelessly move to solve it. When they finish the puzzle, the world will end. The twist ending is that even if the monks are moving one disk per second, it will take them 585 billion years to finish moving the tower. This is a pretty artful way to express the “gotcha” of exponential growth. “Turns out the world isn’t doomed after all!”
And so the puzzle not only demanded a notion of computation, it exhibited a high degree of computational complexity and, lastly, had a familiar popular impact: sublime awe in the face of the immense exponential. All of this does not address one ugly fact, however: The puzzle is very contrived. Next week I’ll look at a much more natural exponential nightmare.