##### What is the Tower of Hanoi?

The Tower of Hanoi (also called Tower of Brahma or Lucas’

Tower) is a mathematical game or puzzle like the one pictured above. The puzzle was first publicized in the West by the French mathematician Édouard Lucas in 1883.

##### The Rules of the Game

The game or puzzle consists of three pegs and a number of disks of different sizes which are to be slid onto any peg. The puzzle starts with the disks in a stack in ascending order of size on one peg, the

smallest at the top and the largest at the bottom. See the picture above.

##### Objective of the Game

The objective of the puzzle is to move the entire stack of disks

to another peg following these simple rules:

- Only one disk can be moved at a time
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack. (a disk can only be moved if it is the uppermost disk on a stack)
- No disk may be placed on top of a smaller disk.

##### The Legend Surrounding Tower of Hanoi

Supposedly there is an ancient prophecy related to the Tower of Hanoi and it is the reason it is alternatively known as the Tower of Brahma. The legend states that Brahmin priests are working at solving the Tower of Hanoi puzzle with 64 disks. As the tale so happens to be told when the last move of the puzzle is completed by these Brahmin priests the world will supposedly end. However, if this legend were true, and if the priests were able to move the disks at a rate of one per second, using the smallest number of moves, it would take them seconds or roughly 585 billion years. That’s quite a long time! So the end of the world is not quite near just yet.

The Tower of Hanoi is popular in computer science and it has a simple and elegant recursive algorithm that is easy to implement.

##### The Recursive Algorithm of Tower of Hanoi

1. move n-1 discs from peg 1 to peg 3

2. move disc n from peg 1 to peg 2

3. move n-1 discs from peg 3 to peg 2

As you can see there is not much to solving the Tower of Hanoi. It requires some ingenuity to arrive at the recursive version of this algorithm but it is straightforward once you understand it. I have implemented it in Java below. In the example below I have chosen to use n=3 discs. When you run this program it will show you the 7 steps that are required to solve the puzzle for the case of 3 discs.

##### Java Implementation of Tower of Hanoi

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public class TOH { public static void TOH(int n, int pegone, int pegtwo, int pegthree) { if(n > 0) { // move n-1 rings from peg one to peg three using peg two TOH(n-1,pegone,pegthree,pegtwo); // move peg n from peg one to peg two System.out.println("move disk from " + pegone + " to " + pegtwo); // move n-1 rings from peg three to peg two using Peg one TOH(n-1,pegthree,pegtwo,pegone); } } public static void main(String[] args) { int n = 3; final int PEGONE = 1; final int PEGTWO = 2; final int PEGTHREE = 3; TOH(n,PEGONE, PEGTWO, PEGTHREE); } } |

At this point you should wonder if that is the minimum number of steps to solve the puzzle for the case of 3 discs. For the case of 3 discs, 7 moves is indeed the miminum number. But is there a general formula to describe this minimum number of moves? The answer is indeed yes. It can be shown and proved that the minimum number of moves to solve the Tower of Hanoi in general is moves, where n is the number of disks.

There is a recurrence relation for the recursive algorithm which is the following: . This relation can be solved through repeated substitution of the recurrence relation.

##### Recurrence Relation for Tower of Hanoi

1. (base case)

2. (number of steps in recursive algorithm)

Equation 1 covers the base case (when there are no

rings, you make no moves) and equation 2 covers the

recursive part of the algorithm (there are two n-1 recursive

calls to move the disks plus the movement of the nth disk).

To solve this recurrence relation one needs to repeatedly substitute as follows:

First we calculate the recurrence for n-1 as follows:

Then we substitute the right hand side of that we calculated above into equation 2 of the Tower of Hanoi recurrence relation to arrive at the following:

(original recurrence)

(substituting for )

Simplifying it to the following:

… we then repeat this process of substitution for T_{n-3}, the Tower of Hanoi recurrence would become the following:

… and after r substitutions the recurrence would look like this:

Consequently, since unfolding the recurrence requires r = n, this implies substituting n wherever r occurs in the previous step. After substitution this yields the following recurrence:

However, we know T_{0} = 0 from the base case. So replacing T_{0} with 0 above simplifies the recurrence from the previous step further to the following:

As you can see after the simplification this last line results in a geometric series. To solve the above geometric series we can employ a simple little trick by taking the difference of two different geometric series as shown below. By rearranging and rewriting the geometric series derived in the last line above as and twice then we get the following two equations.

(a)

(b)

——————————————————-

(the difference of b -a)

One can readily see, that by subtracting (a) from (b) all the middle terms get crossed out or eliminated and what is left are the two end terms. Consequently, after subtraction one is left with . Therefore, the closed form solution for the Tower of Hanoi problem is: .

The above analysis in the end shows that the recursive algorithm of the Tower of Hanoi puzzle is an exponential algorithm and will take a very long time for any larger values of n. The minimum number of moves required to solve the Tower of Hanoi puzzle is calculated using the formula for any number of discs . Using this formula for the simple case of 3 discs it turns out there are indeed moves. One can easily verify that 7 moves is indeed the minimum number for three discs and running the program on that input also validates the result. For those wanting to read more about the Tower of Hanoi there is an excellent book available called The Tower of Hanoi – Myths and Maths.