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.
It is good to understand how recursive solutions are arrived at and how parameters for this recursion are implemented.
The basics of the problem is that you have a board with three pegs in it, and a series of discs. The rule is that the discs are of different sizes and smaller discs must be placed on top of larger discs or an empty peg.
The game starts with all of 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, shown below. With a little work, can you figure out that the Big O for this algorithm is 2^n – 1. That’s a fairly inefficient algorithm, but it’s the only known way to solve the problem.
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.
Tower of Hanoi was originally found on Access 2 Learn
