Math Lesson #6: Tower of Hanoi

Goal: move the stack of discs from "source" peg to "target" peg

Rules: a) move only one disc at time, b) never put bigger disc on top of a smaller

Questions: a) how to do it? b) how many moves needed for stack of n discs?

Let's gain intuition, by solving simpler versions...

A) stack of one disc... easy, just move lone disc... number of moves = 1

B) stack of two discs... move smallest to spare peg, base disc to target, smallest to target... number of moves = 3

C) stack of 3 discs... move smallest to target peg, middle to spare peg, smallest on top of middle disc, base disc to target, smallest to source peg, middle disc to target, smallest disc to target... number of moves = 7

Another way to describe this is: to solve the stack of n discs, solve the n-1 to the spare, then move the base disc and then solve the n-1 to the target:

This leads to a recursive function to count the moves needed:

H( n ) = H( n-1) + 1 + H( n-1)

H( 1 ) = 1

Coding this in Python:

Running hanoi( 9 ) tells us that solving our stack of 9 discs will take 511 moves...

Legend says that in the tower of Brahma, there is a stack of 64 golden discs. Monks work tirelessly moving the discs day and night. The world will end when the monks complete their task. To solve 64 discs will take 18.5 quintillion moves... if eack move takes a second, it will take the monks 585 billion years...