Towers of Hanoi

This famous mathematical game is described in wikipedia. Briefly, we have three pegs and N disks. We wish to move the whole stack of disks to a different peg, let's say # 3. The rules are:

• Only one disk may be moved at a time.
• Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
• No disk may be placed on top of a smaller disk.

For example, here is an intermediate stage in the game with 4 disks. Can you see the three moves that brought us to this point?



A couple of interesting things: one is the recursive nature of Towers of Hanoi. If you already know how to solve the game with N disks, then how do you solve the game with N+1?

Easy, move the first N disks to peg # 2, then move disk N+1 to peg # 3, then move all the other N disks on top. This stereotyped pattern leads to the following visual aid. (I've forgotten where I saw it). It looks like a binary ruler.



This version of the ruler describes the series of moves (though not the target pegs) for the N=4 game. To extend it, add a new bar of the correct height for N = 5, then duplicate all the bars we already have.

The number of moves grows rapidly:

N moves 1 1 2 3 3 7 4 15 N 2N-1

According to wikipedia:

The puzzle was invented by the French mathematician Édouard Lucas in 1883. There is a legend about a Vietnamese temple which contains a large room with three time-worn posts in it surrounded by 64 golden disks. The monks of Hanoi, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the rules of the puzzle, since that time. The puzzle is therefore also known as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle is completed, the world will end.

We can calculate, at one move per second, this game will take roughly 292 billion years, about 20 times the current age of the universe.

>>> x = 3600*24*365 >>> x 31536000 >>> 2**63/x 292471208677L