Question

Write two Java programs ( Iterative and Recursive programs ) that solves Tower of Hanoi problem?use 4 disks and 3 bars

Answer 1

Code recursive:

class Main 
{ 
    // recursive method 
    static void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) 
    { 
        if (n == 1) 
        { 
            System.out.println("Move disk 1 from rod " +  from_rod + " to rod " + to_rod); 
            return; 
        } 
        towerOfHanoi(n-1, from_rod, aux_rod, to_rod); 
        System.out.println("Move disk " + n + " from rod " +  from_rod + " to rod " + to_rod); 
        towerOfHanoi(n-1, aux_rod, to_rod, from_rod); 
    } 
      
    //  Driver method 
    public static void main(String args[]) 
    { 
        int n = 4; // Number of disks 
        towerOfHanoi(n, 'A', 'C', 'B');  // A, B and C are names of rods 
    } 
} 

code screenshot:

output recursive:

Code iterative:

class Main{
     
    // stack representation
    class Stack
    {
        int capacity;
        int top;
        int array[];
    }
     
    // Function to create a stack of given capacity.
    Stack createStack(int capacity)
    {
        Stack stack = new Stack();
        stack.capacity = capacity;
        stack.top = -1;
        stack.array = new int[capacity];
        return stack;
    }
     
    //checking if stack is full
    boolean isFull(Stack stack)
    {
        return (stack.top == stack.capacity - 1);
    }
     
    //checking if stack is empty
    boolean isEmpty(Stack stack)
    {
        return (stack.top == -1);
    }
     
    //adding item to the stack
    void push(Stack stack, int item)
    {
        if (isFull(stack))
            return;
             
        stack.array[++stack.top] = item;
    }
     
    // Function to remove an item from stack.It decreases top by 1
    int pop(Stack stack)
    {
        if (isEmpty(stack))
            return Integer.MIN_VALUE;
             
        return stack.array[stack.top--];
    }
     
    // function to implement legal movement between two poles
    void moveDisksBetweenTwoPoles(Stack src, Stack dest, 
                                  char s, char d) 
    {
        int pole1TopDisk = pop(src);
        int pole2TopDisk = pop(dest);
     
        // When pole 1 is empty
        if (pole1TopDisk == Integer.MIN_VALUE) 
        {
            push(src, pole2TopDisk);
            moveDisk(d, s, pole2TopDisk);
        }
         
        // When pole2 pole is empty
        else if (pole2TopDisk == Integer.MIN_VALUE) 
        {
            push(dest, pole1TopDisk);
            moveDisk(s, d, pole1TopDisk);
        }
         
        // When top disk of pole1 > top disk of pole2
        else if (pole1TopDisk > pole2TopDisk) 
        {
            push(src, pole1TopDisk);
            push(src, pole2TopDisk);
            moveDisk(d, s, pole2TopDisk);
        }
        // When top disk of pole1 < top disk of pole2
        else
        {
            push(dest, pole2TopDisk);
            push(dest, pole1TopDisk);
            moveDisk(s, d, pole1TopDisk);
        }
    }
     
    // Function to show the movement of disks
    void moveDisk(char fromPeg, char toPeg, int disk)
    {
        System.out.println("Move the disk " + disk + 
                                " from " + fromPeg + 
                                  " to " + toPeg);
    }
     
    // Function to implement TOH puzzle
    void tohIterative(int num_of_disks, Stack
                      src, Stack aux, Stack dest)
    {
        int i, total_num_of_moves;
        char s = 'A', d = 'B', a = 'C';
      
        // If number of disks is even, then 
        // interchange destination pole and
        // auxiliary pole
        if (num_of_disks % 2 == 0)
        {
            char temp = d;
            d = a;
            a  = temp;
        }
        total_num_of_moves = (int)(Math.pow(
                             2, num_of_disks) - 1);
      
        // Larger disks will be pushed first
        for(i = num_of_disks; i >= 1; i--)
            push(src, i);
      
        for(i = 1; i <= total_num_of_moves; i++)
        {
            if (i % 3 == 1)
              moveDisksBetweenTwoPoles(src, dest, s, d);
      
            else if (i % 3 == 2)
              moveDisksBetweenTwoPoles(src, aux, s, a);
      
            else if (i % 3 == 0)
              moveDisksBetweenTwoPoles(aux, dest, a, d);
        }
    }
     
    // Driver code
    public static void main(String[] args)
    {
         
        // Input: number of disks
        int num_of_disks = 4;
         
        Main m = new Main();
        Stack src, dest, aux;
         
        // Create three stacks of size 'num_of_disks'
        // to hold the disks
        src = m.createStack(num_of_disks);
        dest = m.createStack(num_of_disks);
        aux = m.createStack(num_of_disks);
         
        m.tohIterative(num_of_disks, src, aux, dest);
    }
    }

output iterative:

code screenshot iterative: