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.

--

--

r&d blog on architecture, software engineering and inspirations

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
stine

stine

11 Followers

r&d blog on architecture, software engineering and inspirations