Algorithm to solve Tower of Hanoi Problem

Posted By on October 20, 2014


Download PDF
Backtracking method for solving Eight Queens Problem
Backtracking Algorithm

 

  • The Tower of Hanoi problem
    • Problem description:
      • There are 3 pegs
      • There are N disks stacked on the first peg. (The disks has a hole in the center).

        Note:

        • Each disk has a different diameter

      • Initially situation:

      • Problem Hanoi(N):
        • Move the N disks from peg 1 to peg 3
        • You must obey a set of rules.

      • Tower of Hanoi Rules:
        • You can only move one disk at a time (from any peg to any other peg), and
        • You may not stack a smaller disk on top of a larger disk






  • Hands on experiment with the Tower of Hanoi
    • See how a Tower of Hanoi of 4 disks is solved:

    • Here is a web site with a nice Tower of Hanoi applet for you to try: click here
    • I have a local Hanoi applet if the above one fails to work: click here






  • Formulating the Tower of Hanoi algorithm – step 1:     input and output
    • Problem description:
      • Write a method to obtain the steps to solve Tower of Hanoi problem of moving n disks from peg 1 to peg 3

      Example:

      • Problem:
        • Move 3 disks from peg 1 to peg 3

      • Solution:
          Move 1 disk:
        
                     1 -> 3
                     1 -> 2
                     3 -> 2
                     1 -> 3
                     2 -> 1
                     2 -> 3
                     1 -> 3
        

      Try out the moves with this applet: click here


    • We will first figure out the following:
      • What input information does the algorithm need to solve the problem.
      • What output information does the algorithm need to return to the user.

      In other words:

      • What are the input parameters ?
      • What is the return type ?

    • Input and output information:
      1. We may as well select an (appropriate) method name to go with the input and output…(Together, they will form the header of the Java method)

        Let’s pick this name:

             hanoi
        

      2. What information does the method need to perform the task – i.e: what are its input parameters ?
        • nDisks = the number of disks that need to be moved
        • fromPeg = the identifier (index) of the peg where the disks originate
        • toPeg = the identifier (index) of the peg where the disks are moved to

        Example: how to express some Tower of Hanoi problems

             hanoi( 10, 1, 3 )        move 10 disks from peg 1 to peg 3
             hanoi( 15, 1, 3 )        move 15 disks from peg 1 to peg 3
             hanoi( 15, 1, 2 )        move 15 disks from peg 1 to peg 2
        

      3. Finally, what is the type of the information do you want to obtain from the method — i.e. what is the return type ?
        • We want to know how to move the disks
        • Example: how to move 3 disks from peg 1 to peg 3:
             1 -> 3
             1 -> 2
             3 -> 2
             1 -> 3
             2 -> 1
             2 -> 3
             1 -> 3
          

          What is the type of this information ???

          • Answer: String !!!

        • The return type is String


    • Header of the method:
          public static String hanoi( int nDisks, int fromPeg, int toPeg )
          {
              ....
          }
      

      The meaning of the input parameters are:

      • nDisks = number of disks to move
      • fromPeg = the starting peg number where the nDisks disks are moved
      • toPeg = the destination peg number where the nDisks disks are moved






  • Formulating the Tower of Hanoi algorithm – step 2:     develop the solution
    • Solution method:
      • Because this lecture is on recursive algorithm, you can kinda guess that the solution will be a recursive algorithm.

    • Because the Tower of Hanoi problem is more complicated than factorial or fibonacci, I will follow the steps given in the general procedure more carefully to help you see how the solution is put together.Here are the general step to write a recursive algorithm – summarized for your convenience:
      1. Find out which smaller Tower of Hanoi problems you need to use to solve the original Tower of Hanoi problem
      2. Find out how to use the solutions of the smaller Tower of Hanoi problems to solve the original Tower of Hanoi problem.
      3. Find the solutions for a sufficient number of the base cases.






    • Step 1: Identifying a smaller Tower of Hanoi problem within the Tower of Hanoi problem:
      • The original Tower of Hanoi problem: move N disks

      • A smaller Tower of Hanoi problem: move N-1 disks


    • Step 2: figure out how to use the solution of the smaller Tower of Hanoi (N−1 disks) problem to solve the original Tower of Hanoi (N disks) problem.
      • The original Tower of Hanoi (N disks) problem:

      • The effect of the solution of the smaller Tower of Hanoi (N−1 disks) problem is:Case 1:
        Before After

        Case 2:

        Before After

        Think a little bit….

        • How can use use the solution of case 1 or case 2 to solve the original Tower of Hanoi problem ???


      • Answer: How to use the solution the smaller Tower of Hanoi (N−1 disks) problem to solve the original Tower of Hanoi (N disks) problem:
        • First, solve this smaller Tower of Hanoi (N−1 disks) problem:
          Before After


        • Next: move one disk from peg 1 to peg 3
          Before After


        • Finally: solve this smaller Tower of Hanoi (N−1 disks) problem:
          Before After


    • Step 3: find base cases (we need one base case – because the smaller problem has the size N−1)
      • Move stack of disks that has 1 disk is very easy:






  • The recursive solution for the Tower of Hanoi problem
    • Terminology:
      • from peg = the source peg in a Tower of Hanoi problem.
      • to peg = the destination peg in a Tower of Hanoi problem.
      • help peg = the peg in a Tower of Hanoi problem that is not a source or destination peg.

      • Example:
        • hanoi(n, 1, 3) means the Tower of Hanoi problem of moving n disks from peg 1 to peg 3
        • The from peg = 1
        • The to peg = 3
        • The help peg = 2

    • Pseudo code:
         String hanoi( int nDisks, int fromPeg, int toPeg )
         {
      
             int helpPeg;
      
             if ( nDisks == 1 )
             {
                /* ------------------------------------------------------
      	     Solving a trivial (base case) Tower of Hanoi problem:
                       
      	     ------------------------------------------------------ */
      	  return( "Do this move: fromPeg --> toPeg" );
             }
             else
             {
                /* ------------------------------------------------
      	     Solving a non-trivial Tower of Hanoi problem:
                        
                   ------------------------------------------------ */
      
                /* ------------------------------------------------
                   Determine the helpPeg
      	     ------------------------------------------------ */
                helpPeg = peg index that is not equal to fromPeg and toPeg;
      
                /* ---------------------------------------------------
      	     First: solve this smaller Tower of Hanoi problem:
                        
                   ---------------------------------------------------- */
                sol1 = hanoi( nDisks-1, fromPeg, helpPeg );  // Sol1 looks like: 1 -> 3, 1 -> 2, ...
      
                /* ---------------------------------------------------
      	     Next: do this move
                        
                   ---------------------------------------------------- */
                myStep = "Do this move: fromPeg --> toPeg";
      
                /* ---------------------------------------------------
      	     Finally: solve this smaller Tower of Hanoi problem:
                        
                   ---------------------------------------------------- */
                sol2 = hanoi( nDisks-1, helpPeg, toPeg );    // Sol2 looks like: 1 -> 3, 1 -> 2, ...
      
                /* ===============================================
      	     How to use the solutions sol1 and sol2 to
                   solve hanoi(nDisks, fromPeg, toPeg):
      	        1. first making the moves in sol1
      		2. then do myStep
      		3. finally, do the moves in sol2
                   =============================================== */
                mySol = so1l + myStep + sol2;    // mySol looks like: 1 -> 3, 1 -> 2, ...
      
      	  return ( mySol );
             }
      

 

Backtracking method for solving Eight Queens Problem
Backtracking Algorithm

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com