Algorithm for Tower of Hanoi

Tower of Hanoi was a mathematical puzzle invented by Lucas 1883, France. There are many legends and myths about it as well. One myth I know is that the world will end if 64 tower disks’ Tower of Hanoi is completed. Lets see why the myth could be true.

Algorithm

A1: If the number of disks is even, move the first disk to tower 2. If the number of disks is odd, move the first disk to tower 3.

A2: All other numbers of disks have this same pattern: first move all disks except the base disk to tower 2, then move the base disk to tower 3.

A3: If the number of disks is even, move the smallest disks to tower 1. If the number of disks is odd, move the smallest disk to tower 3, and continue.

The patterns

A4: To find the minimum number of times to move the disk, follow this pattern

1 disk = move 1 time

2 disks = (1 x 2) + 1 = 3 times

3 disks = (3 x 2) + 1 = 7 times

4 disks = (7 x 2) + 1 = 15 times

5 disks = (9 x 2) + 1 = 31 times

…And so on. So the pattern is ‘{(the previous number of times) x 2} + 1’.

A5: There are other things you can do with this pattern…like calculating how many times you need to move 64 disks. Let’s start off with 1 disk and find the pattern…

1 disk (1 time) + 1 = (0+1) x 2 = 2 = 21

2 disks (3 times) + 1 = (1+1) x 2 = 4 = 22

3 disks (7 times) + 1 = (3+1) x 2 = 8 = 23

4 disks (15 times) + 1 = (7+1) x 2 =16 = 24

So we come up with a formula…

‘n disk: (#min. moves) + 1 = {(previous #min. moves)+1} x 2

Notice that the number required to move n number of disk is 2^n-1

Therefore, the minimum number required to move 64 disks is 2^64–1.