The Question:

There are three towers with ‘n’ disks on the first one. The objective is to move all ‘n’ disks to the third tower. However:

  • You can move only one disk at a time.
  • Only the uppermost disk of a stack can be moved. This means that disks below the uppermost disk cannot be moved without moving the uppermost one.
  • No disk can be placed on top of a smaller disk.

Origins:

“The tower of Hanoi” is a mathematical puzzle that was invented by the French mathematician Édouard Lucas in 1883. However, legend has it that this concept was originally invented by Indian priests who were acting out the command of an ancient prophecy. In the temple there was a large room with 3 posts surrounded by 64 golden disks. The priests move the disks according to the immutable rules of Brahma. It is said once the last move is played the world will end. Hence, the problem is also known as the “Towers of Brahma”. (more information on https://en.wikipedia.org/wiki/Tower_of_Hanoi)

However, there is no need to worry as even if this is true it would take 264-1 seconds (roughly 585 billion years) if the disks are moved at a rate of 1 disk per second. Therefore, we are safe for now :-).

The Algorithm:

The solution to this problem lies in simple recursion. We repeatedly divide the problem into smaller sub-problems and solve those independently, hence, working our way up to solving the final problem.

The function(tower) to solve this will take the following inputs:

  • N – the number of disks
  • From – the tower from which we need to move the ‘n’ disks
  • To – the tower to which we need to take the ‘n’ disks.
  • Auxiliary – the remaining tower.

Hence, it would be tower(n , frm , to , aux)

In our solution we will use arrays to represent the towers and the elements of a particular array will represent the disks of that tower.

The base case of our recursive algorithm will be a check whether n == 1. If so we append the ‘to’ array with the element, print the towers with their disks and end that particular iteration of the function.

For Example:

Consider the problem with n = 3. It would look like:

We will initialise the first tower as A, the second one as B and the third one as C.

To solve the above we call function tower(3, A , C , B)

We can break down the above problem by saying that we have to move the top 2 to B and then move the last one to C and subsequently move the last 2 to C.

Thus we run tower(2 , A , B , C).

We can further break this into moving the topmost disk to C, move 2 to B and subsequently move the first one to B.’

Thus we run tower(1 , A , C , B).

We cannot break this further and hence we move the topmost disk to C.

The towers now look like:

Now, we move onto the task of moving the second disk to B.

Thus, we run tower(1 , A , B , C).

We cannot break this further and hence we move the second disk to B.

The towers now look like:

Next, we have the task of moving the first disk to B, on top of the second disk.

We run tower(1 , C , B , A)

We cannot break this further and hence we move the first disk to B.

The towers now look like:

Now tower(2 , A , B , C) has been run fully.

Next according to  the algorithm we have the task of moving the third disk to C.

Thus we run tower(1 , A , C , B)

We cannot break this further and hence we move the third disk to C.

The towers now look like:

Now all that’s left is the task of moving the 2 disks from B to C.

To do this we run tower(2 , B , C , A)

We can break this problem into the simple problems of moving the first disk to A, then moving the second disk to C and finally moving the first disk to C. (we can only move 1 disk at a time)

To do the first of these tasks, i.e., moving the first disk to A, we will run tower(1 , B , A , C)

We cannot break this further and hence we move the first disk to A.

The towers now look like:

Next, we have to move the second disk to C.

To do this we run tower(1 , B , C , A)

We cannot break this further and hence we move the second disk to C.

The towers now look like:

We have now reached the last step of the algorithm. All that’s left is to move the first disk to C.

To do this we run tower(1 , A , C , B).

We cannot break this further and hence we move the first disk to C.

The towers now look like:

The algorithm is now over!

We have successfully visualised the algorithm behind the solution to the “Tower of Hanoi” problem!

The Program:

n = int(input("Enter the number of disks: "))
A = []
B = []
C = []

for k in range(n):
    A.append(n-k)

print(A,B,C)

def Tower2(n, frm, to, aux):
    if n == 1 :
        to.append(frm.pop())
        print(A,B,C)
        return
    Tower2(n-1, frm, aux, to)
    to.append(frm.pop())
    print(A,B,C)
    Tower2(n-1, aux, to, frm)

Tower2(n, A, C, B)

Output of this program:

This program shows all the steps involved in moving the disks from A to C.

Time complexity of the above program:

T(n) = O(2(n+1) – 1) which can be represented as O(2n) where n is the number of disks

The minimum number of moves needed to solve a “Tower of Hanoi” problem with n disks is 2n – 1

Visits: 137

One Reply to “Tower of Hanoi”

Leave a Reply

Your email address will not be published. Required fields are marked *