Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Tower of Hanoi Implementation in Java

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 5.06k
    Comment on it

    Hi Readers,

    In this blog i will provide you the Java solution for the famous Tower of Hanoi problem using Stack.

    Problem definition

    Tower of Hanoi is a mathematical puzzle. It is also known as Tower of Brahma or Locus' Tower. This puzzle consist of three rods in which disks can slide. There are some number of disks are placed on a rod in increasing order of their disk size form top to bottom. Now we have to transfer all the disk to another rod. Keeping in mind that.

    1. Only one disk can be moved at a time.
    2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
    3. No disk may be placed on top of a smaller disk.

     

     

    Now we have to find the of moves of disks to solve this problem. 

     

    Java Implementation for the above problem

    import java.util.Scanner;
    import java.util.Stack;
    
    public class TowerOfHanoi {
    	public static int N;
    	/* Creating Stack array */
    	public static Stack<Integer>[] tower = new Stack[4];
    
    	public static void main(String[] args) {
    		Scanner scan = new Scanner(System.in);
    		tower[1] = new Stack<Integer>();
    		tower[2] = new Stack<Integer>();
    		tower[3] = new Stack<Integer>();
    		/* Accepting number of disks */
    		System.out.println("Enter number of disks");
    		int num = scan.nextInt();
    		scan.close();
    		N = num;
    		toh(num);
    	}
    
    	/* Function to push disks into stack */
    	public static void toh(int n) {
    		for (int d = n; d > 0; d--)
    			tower[1].push(d);
    		display();
    		move(n, 1, 2, 3);
    	}
    
    	/* Recursive Function to move disks */
    	public static void move(int n, int a, int b, int c) {
    		if (n > 0) {
    			move(n - 1, a, c, b);
    			int d = tower[a].pop();
    			tower[c].push(d);
    			display();
    			move(n - 1, b, a, c);
    		}
    	}
    
    	/* Function to display */
    	public static void display() {
    		System.out.println("  A  |  B  |  C");
    		System.out.println("---------------");
    		for (int i = N - 1; i >= 0; i--) {
    			String d1 = " ", d2 = " ", d3 = " ";
    			try {
    				d1 = String.valueOf(tower[1].get(i));
    			} catch (Exception e) {
    			}
    			try {
    				d2 = String.valueOf(tower[2].get(i));
    			} catch (Exception e) {
    			}
    			try {
    				d3 = String.valueOf(tower[3].get(i));
    			} catch (Exception e) {
    			}
    			System.out.println("  " + d1 + "  |  " + d2 + "  |  " + d3);
    		}
    		System.out.println("\n");
    	}
    
    }

     

    Output of the above program

    Enter number of disks
    5
      A  |  B  |  C
    ---------------
      1  |     |   
      2  |     |   
      3  |     |   
      4  |     |   
      5  |     |   
    
    
      A  |  B  |  C
    ---------------
         |     |   
      2  |     |   
      3  |     |   
      4  |     |   
      5  |     |  1
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
      3  |     |   
      4  |     |   
      5  |  2  |  1
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
      3  |     |   
      4  |  1  |   
      5  |  2  |   
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |   
      4  |  1  |   
      5  |  2  |  3
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
      1  |     |   
      4  |     |   
      5  |  2  |  3
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
      1  |     |   
      4  |     |  2
      5  |     |  3
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |  1
      4  |     |  2
      5  |     |  3
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |  1
         |     |  2
      5  |  4  |  3
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |   
         |  1  |  2
      5  |  4  |  3
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |   
      2  |  1  |   
      5  |  4  |  3
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
      1  |     |   
      2  |     |   
      5  |  4  |  3
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
      1  |     |   
      2  |  3  |   
      5  |  4  |   
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |   
      2  |  3  |   
      5  |  4  |  1
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |  2  |   
         |  3  |   
      5  |  4  |  1
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |  1  |   
         |  2  |   
         |  3  |   
      5  |  4  |   
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |  1  |   
         |  2  |   
         |  3  |   
         |  4  |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |  2  |   
         |  3  |   
      1  |  4  |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |   
         |  3  |  2
      1  |  4  |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |  1
         |  3  |  2
         |  4  |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |  1
         |     |  2
      3  |  4  |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |   
         |  1  |  2
      3  |  4  |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |   
      2  |  1  |   
      3  |  4  |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
      1  |     |   
      2  |     |   
      3  |  4  |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
      1  |     |   
      2  |     |  4
      3  |     |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |  1
      2  |     |  4
      3  |     |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |  1
         |     |  4
      3  |  2  |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |   
         |  1  |  4
      3  |  2  |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |  3
         |  1  |  4
         |  2  |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |   
         |     |  3
         |     |  4
      1  |  2  |  5
    
    
      A  |  B  |  C
    ---------------
         |     |   
         |     |  2
         |     |  3
         |     |  4
      1  |     |  5
    
    
      A  |  B  |  C
    ---------------
         |     |  1
         |     |  2
         |     |  3
         |     |  4
         |     |  5
    

    Finally we have the Java solution for Tower of Hanoi puzzle. :)

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: