Tower of Hanoi

1. Intro

‘Tower of Hanoi’ is a well-known puz­zle pre­sented in many CS text­books. These the rules:
– The are 3 poles A, B, and C.
– n disks are on pole A with the con­i­cal shape (the largest disk is at the bot­tom, then the smaller ones upper, and the small­est on top).
– You job is to move the entire n disks from pole A to pole C (the same con­i­cal shape as the final result) using 3 poles while obey­ing the rules:

+ only one disk is moved at a time
+ no disk is allowed to be placed on top of a smaller one

2. Tips to solve the game

This sim­ple and easy-to-follow guide will guar­an­tee you the least moves (and time if you prac­tice) to achieve the result:

[ Don’t look at this if you pre­fer try­ing the game first ]

+ Focus on the smallest disk and the number n is even or odd
+ Move alternatively between the smallest and other disk
+ Assume pole A is on the left, B middle, and C right side. When move the smallest disk, always in the same direction [to the right if n is even, and to the left if n is odd]. In case there is no pole in this direction, move to the opposite far end. Then resume the normal direction. While you follow this way of the smallest disk's movement, there is only one way to move the non-smallest disk
+ Continue this until the job is done

3. The Legend

There are dif­fer­ent sto­ries about this puz­zle. The com­mon idea is that with n = 64 disks, the world will end if any­one can solve this game (!!)

Assume that each move takes 1 sec­ond. It is proved that the least num­ber of moves required is 2ⁿ — 1 to achieve the result. With n = 64, it would take… 585 bil­lions of years (!!)

4. Intro to Recur­sion concept

5. The Rela­tion­ship between “Tower of Hanoi” and Recursion

6. Algo­rithms to solve this game

7. Final thoughts

To be con­tin­ued
updated 25 Sept. 2011