Sunday 2 September 2012

Tower Of Hanoi - Non-recursive Approach

Tower Of Hanoi

                                                             --  shaikzakir3149@gmail.com


Hello all, this is my first post. Hope you find it useful ...


Implement non-recursive Towers of Hanoi. Given the number n of disks as input, maintain appropriate pegs/rods to simulate the movement of the disks among the three pegs: Source, Auxilary & Destination.
Output the sequence of moves of the disks. Following is an example of the output expected by your program.

No. of disks: 3
Sequence of Moves
1. Source → Destination
2. Source → Auxilary
3. Destination → Auxilary
4. Source → Destination
5. Auxilary → Source
6. Auxilary → Destination
7. Source → Destination

Note: Remember that towers of hanoi can be solved in (2^n - 1) at the best for given n disks.



Algorithm:

While size of Destination is less not equal to n
do
{
If num of disks is even then

       Make legal move between Source and Auxilary
       Make the legal move between pegs Source and Destination

else

        Make the legal move between pegs Source and Destination  
        Make the legal move between pegs Source and Auxilary

endif

Make legal move between pegs Auxilary and Destination



}
end While


Note that a legal move is one which abides by the rules of the puzzle. Only a smaller disk can be moved onto a larger disk.

Running Time Complexity :

 The runtime complexity of this algorithm is O((2^n - 1)/3) which is equivalent to O(2^n). Clearly the stack operations (push, pop and peek) have a runtime equal to O(1).

The code is given in Java.


Source Code :


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
//package tower.of.hanoi;
import java.io.*;
import java.util.Stack;
import java.util.EmptyStackException;
/**
 *
 * @author Shaik
 */
public class TowerOfHanoi {

    
    public static int legalMove(Stack A, Stack B)
    {
        int a,b;
        try {
        a = Integer.parseInt(A.peek().toString());
        }
        catch(EmptyStackException e){
        a = 0;    
        }
        try {
            b = Integer.parseInt(B.peek().toString());
        }
        catch(EmptyStackException e){
        b = 0;    
        }
        if(a==b) return 0;
        if(a == 0)             // If peg A is empty, then pop from B and push the disk onto A
    {
        A.push(B.pop());
            return 2;           // Return 2 as move occurred from B to A
    }
        else if(b == 0)        // If peg B is empty, then pop from A and push the disk onto B
        {
        B.push(A.pop());
        return 1;           // Return 1 since move occurred from A to B
    }
        
        if(a<b)
        {
        B.push(A.pop());
        return 1;               // Return 1 since move occurred from A to B
        }
        else if(a > b)            // value of top disk of peg A is greater than the value of topmost disk of peg B
        {
        A.push(B.pop());
        return 2;               // Return 2 since move occurred from B to A
        }
        return -1;
    }
        
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        int stepNumber = 0;
        int status = 0;
        try {
        Stack Source = new Stack();
        Stack Auxilary = new Stack();
        Stack Destination = new Stack();
        
        System.out.println("Enter the number of disks : ");
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(input.readLine());
        if(n<=0)
        {
            System.out.println("Sorry wrong input, negative numbers not allowed.");
            System.exit(1);
        }
        for(int i=n; i>0; i--)
            Source.push(i);
        int m = n%2;
        do {
            if(m==1)
            {
                if((status = legalMove(Source,Destination)) == 1)
                    System.out.println((++stepNumber) + ". Source --> Destination");
                else if (status == 2)
                    System.out.println((++stepNumber) + ". Destination --> Source");
                
                if((status = legalMove(Source,Auxilary)) == 1)
                    System.out.println((++stepNumber) + ". Source --> Auxilary");
                else if(status == 2)
                    System.out.println((++stepNumber) + ". Auxilary --> Source");
                else 
                    break;
            }
            
            else
            {
                if((status = legalMove(Source,Auxilary)) == 1)  
                    System.out.println((++stepNumber) + ". Source --> Auxilary");
                else if (status == 2)
                    System.out.println((++stepNumber) + ". Auxilary --> Source");
                
                if((status = legalMove(Source,Destination)) == 1)
                    System.out.println((++stepNumber) + ". Source --> Destination");
                else if(status == 2)
                    System.out.println((++stepNumber) + ". Destination --> Source");
                
            }
            
            if((status = legalMove(Auxilary,Destination)) == 1) 
                System.out.println((++stepNumber) + ". Auxilary --> Destination");
            else if(status == 2)
                System.out.println((++stepNumber) + ". Destination --> Auxilary");
        }while(Destination.size()!=n);
        System.out.println("X-----------------------X");
        }         

        catch (Exception e){
        }
        }
    }


8 comments:

  1. Hi thanks for the post but can you help me trace your code some parts that i do not understand thanks

    ReplyDelete
    Replies
    1. Erick, Which part of code you did not understand? Can you share some details?

      Delete
  2. i required the Non Recursive Tower Of Hanio Code in C- Language

    Please can u provide me immediately...@ my email id
    bharsakaleaniket@gmail.com

    ReplyDelete
    Replies
    1. Hi Aniket,

      I think you want it: http://www.ebah.com.br/content/ABAAAgEMoAJ/torres-hanoi-nao-recursiva

      Delete
  3. hi can u make the honoi tower in stack using class

    ReplyDelete
  4. hi can u make the honoi tower in stack using class

    ReplyDelete
  5. I played the Hanoi Tower game a few times and only found that there is a difference between the odd and even numbers, but I didn't find a rule that allowed me to write code. Your legal move is really awesome, but it feels more difficult to understand than recursive. Thank you very much, I have learned a lot

    ReplyDelete