Tower of Hanoi

The Tower of Hanoi, sometimes called the Tower of Brahma puzzle, is one of the classic problems to look at if you want to learn recursion.

This problem is good to understand how recursive solutions are arrived at and how parameters for this recursion are implemented. We look at the solution in another post.

The basis of the problem is that you have a board with three pegs in it and a series of discs. The discs are of different sizes and smaller discs can only be placed on top of larger discs or on an empty peg. Something as simple as three to ten pegs if often used as a child’s toy. The game can even be found on Amazon.

The game starts with all the discs on one peg, and the goal is to get the disk onto another peg with the discs in the right order. With each move, you can only move a single disc.

Simulating the Problem

Let’s say you had three pegs, labeled A, B and C. Then you have two discs on Peg A, 1 and 2, with two on the bottom because it is a larger number.

You could:

        Move disc 1 from A to B

        Move disc 2 from A to C

        Move disc 1 from B to C

As you add discs however, this becomes more and more complex requiring more moves.

Assume you have 3 discs: 1, 2 and 3.

        Move disc 1 from A to C

        Move disc 2 from A to B

        Move disc 1 from C to B

        Move disc 3 from A to C

        Move disc 1 from B to A

        Move disc 2 from B to C

        Move disc 1 from A to C

With 2 discs, we had 3 moves. With 3 discs, we had 7 moves. Add a fourth disc and now you have 15 steps to process, as shown below. With a little work, can you figure out that the Big O for this algorithm is 2ⁿ – 1. That’s a fairly inefficient algorithm, but it’s the only known way to solve the problem. When we remove the constant, which is done in calculating Big O, this gives of an exponential problem of 2ⁿ.

        Move disc 1 from A to B

        Move disc 2 from A to C

        Move disc 1 from B to C

        Move disc 3 from A to B

        Move disc 1 from C to A

        Move disc 2 from C to B

        Move disc 1 from A to B

        Move disc 4 from A to C

        Move disc 1 from B to C

        Move disc 2 from B to A

        Move disc 1 from C to A

        Move disc 3 from B to C

        Move disc 1 from A to B

        Move disc 2 from A to C

        Move disc 1 from B to C

It is said that this game is being run by monks with 64 discs. When they complete the task, the end of the world occurs. However, this would take 18,446,744,073,709,551,615 moves. If one move occurred per second, it would take approximately 584,942,417,355 years if my math is correct, or almost 585 billion years to solve.

To give you an idea of the type of scale, the sun is estimated to only have 5 billion years of fuel left, before it becomes a Red Giant, and engulfs Mercury, Venus, and possibly Earth. Whether it does, or doesn’t, engulf us won’t matter. Life as we know it won’t be able to survive. [source] So we don’t have to worry about that end of the world scenario, we have our own… not that I’ll be alive for it myself.

Tower of Hanoi was originally found on Access 2 Learn