Data Structure & Algorithms - Tower of Hanoi

Data Structure & Algorithms - Tower of Hanoi

§  In this blog tutorial we will discuss about Tower of Hanoi problem so I am going to show you how to write an algorithm for Tower of Hanoi by taking a small example as well as large example with 3 disc.

§  The problem is there are three Towers given and one of the tower is having a stack of disc in the decreasing order of the sizes from bottom towards top we have to move all this disc from Tower A to Tower C and at any moment of time a larger disc should not be kept over small disc so this will not be easy to transfer all this disc so for  help one more auxiliary Tower is given .

§  First of all, we solve this problem by taking a small example with 2 disc.

Step-1:

 §  Move a disc from TowerA to TowerB using TowerC.

Step-2:

 §  Move a disc from TowerA to TowerC.

   Step-3:

 §  Move a disc from TowerB to TowerC using TowerA.

 v Now solve problem when there are three disc are given. if there are three disc given now we can call this problem little bit complex problem.

   Move 2 disc from TowerA to TowerB using TowerC

 §  move two disc from A to B using C actually we have to move one disk at a time but here I am saying move two disc. how to move two disk from one tower to another Tower already have seen it so you can apply that procedure  so its means this statement is recursive statement so it's not talking about one disc at a  time here is talking two disc at a time .so how to move to 2 disc  I have already seen the procedure so let us see two disc move hear this is done.

       Move 2 disc from TowerA to TowerB using TowerC

 §  Move a disc from TowerA to TowerC

 §  Move 2 Disc from TowerB to TowerC using TowerA

 §  Now these three steps are very important for devising a recursive procedure for Tower of Hanoi problem.

 §  If there are n disc than those three steps can be written like this.

Ø Move n-1 disc from TowerA to TowerB using TowerC.

Ø Move a disc from TowerA to TowerC

Ø Move n-1 disc from TowerB to TowerC using TowerA

 §  this is recursive algorithm for Tower of Hanoi.

A recursive algorithm for Tower of Hanoi can be driven as follows −

TowerA - Source Tower

TowerB - Auxiliary Tower

TowerC- Destination Tower

n- number of disc

START

Procedure TOH(n, TowerA, TowerB, TowerC)

   IF disc == 1, THEN

      move disk from TowerA, to TowerC

   ELSE

      Move n-1 disc from TowerA to TowerB using TowerC.

      TOH(n - 1, TowerA ,TowerC ,TowerB)     // Step 1

      move disk from TowerA to TowerC              // Step 2

     Move n-1 disc from TowerB to TowerC using TowerA

      Hanoi(disk - 1, TowerB , TowerA , TowerC)     // Step 3

   END IF

END P

 
Program for Tower of Hanoi

def TOH(n,A,B,C):

    if n>0:

        TOH(n-1,A,C,B)

        print("[{}-{}]".format(A,C))

        TOH(n-1,B,A,C)

TOH(3,1,2,3)
Output:

[1-3]

[1-2]

[3-2]

[1-3]

[2-1]

[2-3]

[1-3]

• email
• facebook
• linkedin
• twitter
• reddit
• google+

Author Name

Author Description!

Get Free Email Updates to your Inbox!

• Rss
• Twitter
• FaceBook
• Google +