Question

Write two Java programs ( Iterative and Recursive programs ) that solves Tower of Hanoi problem?use 4 disks and 3 bars.
Students must send the code and outputs

Answer 1

Greetings!!!!!!!!!!

Please find below the Iterative approach (program) to Tower of Hanoi with screen shot of sample run. It is for 4 disks and 3 bars.

public class Main
{
    
     // A structure is defined to indicate a stack
    class intermediateStack
    {
        int size;
        int top;
        int array[];
    }

    // Function to create a stack of given maximum capacity.
    intermediateStack createStack(int max)
    {
        intermediateStack stack = new intermediateStack();
        stack.size = max;
        stack.top = -1;
        stack.array = new int[max];
        return stack;
    }

    // Stack is full when the top is equal to the size - 1 (last index)
    boolean isFull(intermediateStack stack)
    {
        return (stack.top == stack.size - 1);
    }

    // Stack is empty when top is equal to -1
    boolean isEmpty(intermediateStack stack)
    {
        return (stack.top == -1);
    }

    // Function to push an item into the stack. 
    // It also increases value of top by 1
    void push(intermediateStack stack, int valItem)
    {
        if (isFull(stack))
                return;
                
        stack.array[++stack.top] = valItem;
    }

    // Function to pop an item from the stack.
    // it also decreases top by 1
    int pop(intermediateStack stack)
    {
        if (isEmpty(stack))
                return Integer.MIN_VALUE;
                
        return stack.array[stack.top--];
    }

    // Function to implement legal movement between two bars
    void moveDisksBetweenTwoBars(intermediateStack src, intermediateStack dest, String source, String destination) 
    {
        int bar1TopDisk = pop(src);
        int bar2TopDisk = pop(dest);
    
        // When bar 1 is empty
        if (bar1TopDisk == Integer.MIN_VALUE) 
        {
                push(src, bar2TopDisk);
                moveDisk(destination, source, bar2TopDisk);
        }
        
        // When bar 2 is empty
        else if (bar2TopDisk == Integer.MIN_VALUE) 
        {
                push(dest, bar1TopDisk);
                moveDisk(source, destination, bar1TopDisk);
        }
        
        // When top disk of bar 1 > top disk of bar 2
        else if (bar1TopDisk > bar2TopDisk) 
        {
                push(src, bar1TopDisk);
                push(src, bar2TopDisk);
                moveDisk(destination, source, bar2TopDisk);
        }
        // When top disk of bar 1 < top disk of bar 2.
        else
        {
                push(dest, bar2TopDisk);
                push(dest, bar1TopDisk);
                moveDisk(source, destination, bar1TopDisk);
        }
    }

    // Function to show the movement of disks between bars
    void moveDisk(String from, String to, int disk)
    {
        System.out.println("Move the disk " + disk + 
                                                        " from " + from + 
                                                        " to " + to);
    }

    // Function to implement Tower Of Hanoai problem.
    void iterativeTOH(int number_of_disks, intermediateStack src, intermediateStack aux, intermediateStack dest)
    {
        int x, total_number_of_moves;
        String s = "Source Bar";
        String d = "Destination Bar";
        String a = "Auxiliary Bar";
    
        // If number of disks is even, then 
        // interchange destination bar and auxiliary bar
        if (number_of_disks % 2 == 0)
        {
                String temp = d;
                d = a;
                a = temp;
        }
        total_number_of_moves = (int)(Math.pow(2, number_of_disks) - 1);
    
        // Larger disks will be pushed first
        for(x = number_of_disks; x >= 1; x--)
                push(src, x);
    
        for(x = 1; x <= total_number_of_moves; x++)
        {
                if (x % 3 == 1)
                moveDisksBetweenTwoBars(src, dest, s, d);
    
                else if (x % 3 == 2)
                moveDisksBetweenTwoBars(src, aux, s, a);
    
                else if (x % 3 == 0)
                moveDisksBetweenTwoBars(aux, dest, a, d);
        }
    }  


    public static void main(String[] args)
    {
        
        // Input: number of disks is given as 4.
        int number_of_disks = 4;
        
        Main ob = new Main();
        intermediateStack source, destination, auxiliary;
        
        // Create three stacks of size 'number_of_disks' (4 in our case)
        // to hold the disks
        source = ob.createStack(number_of_disks);
        destination = ob.createStack(number_of_disks);
        auxiliary = ob.createStack(number_of_disks);
        
        ob.iterativeTOH(number_of_disks, source, auxiliary, destination);
    }
}

Please find below the Recursive approach (program) to Tower of Hanoi with screen shot of sample run. It is for 4 disks and 3 bars.

public class Main
{
    
    // Java recursive function to solve tower of hanoi problem 
    static void TOH(int Number_of_disks, String from_bar, String to_bar, String aux_bar) 
    { 
        if (Number_of_disks == 1) 
        { 
            System.out.println("Move the disk 1 from " +  from_bar + " Bar to " + to_bar + " Bar"); 
            return; 
        } 
        TOH(Number_of_disks-1, from_bar, aux_bar, to_bar); 
        System.out.println("Move the disk " + Number_of_disks + " from " +  from_bar + " Bar to " + to_bar + " Bar"); 
        TOH(Number_of_disks-1, aux_bar, to_bar, from_bar); 
    } 
      
   
    public static void main(String args[]) 
    { 
        //Input: Number of Disks is given as 4.
        int n = 4; 
        
        // Source, Auxiliary, and Destination are names of bars.
        TOH(n, "Source", "Destination", "Auxiliary");  
    } 
}

Thank You