Solving Tower Of Hanoi problem

Hello Friends,

Lets see how to solve the famous tower of Hanoi Problem.

Suppose there are three Pegs (or towers), namely Source, Middle and Destination. Initially peg A has few  disks stacked on it. The stack of the disks are such that the largest disk is at the bottom. As we move towards the top the size of the disks decreases.

The objective of this problem is to shift the disks from Source to destination using middle Peg using below rules.

Only one Disk can be shifted from one Peg to another. A Disk can not be added to the peg if the size of the disk at the top of that Stack is less than the size of the disk we wish to add.

Lets See the code below :)

For the understanding we will use a class Tower which will be implementation of Stack.

public class Tower {
  int tower[];
  int numDisks;
  int top = -1;
  String name;

  public Tower(int numDisks, String name) {
   this.numDisks = numDisks;
   tower = new int[numDisks];
   this.name = name;
  }

  public void addDisk(int disk) {
   System.out.println("adding   "+disk+" on tower   : "+name);
   tower[++top] = disk;
  }

  public int removeDiskOnTop() {
   int diskOnTop = tower[top];
   System.out.println("removing "+diskOnTop+" from tower : "+name);
   top--;
   return diskOnTop;
  }

  public void print() {
   if (top == -1) {
    System.out.println(name + " Tower is empty");
   } else {
    System.out.print(name + " tower contains... ");
    for (int i = 0; i <= top; i++) {
     System.out.print(tower[i] + " ");
    }
    System.out.println();
   }
  }
}

Now lets create a class TowerOfHanoi  and put above defined class Tower in it as an static inner class and solve Tower of Hanoi [initial version for understanding, we will see final implementation after this.]

See How tower of Hanoi is solved for number of disks  equal to 2 , or 3 or 4 and how the solution solving the Tower of Hanoi with number of disks equal to 3 is used to solve the problem for number of disks = 4. Like wise note how problem for number of disks = 2 is used to solve the problem for number of disks = 3.

package com.algorithm.recurrsion;

public class TowerOfHanoi {
 public static class Tower {
  int tower[];
  int numDisks;
  int top = -1;
  String name;

  public Tower(int numDisks, String name) {
   this.numDisks = numDisks;
   tower = new int[numDisks];
   this.name = name;
  }

  public void addDisk(int disk) {
   System.out.println("adding   "+disk+" on tower   : "+name);
   tower[++top] = disk;
  }

  public int removeDiskOnTop() {
   int diskOnTop = tower[top];
   System.out.println("removing "+diskOnTop+" from tower : "+name);
   top--;
   return diskOnTop;
  }

  public void print() {
   if (top == -1) {
    System.out.println(name + " Tower is empty");
   } else {
    System.out.print(name + " tower contains... ");
    for (int i = 0; i <= top; i++) {
     System.out.print(tower[i] + " ");
    }
    System.out.println();
   }
  }
 }

 Tower source;
 Tower middle;
 Tower destination;

 int numDisks;

 public TowerOfHanoi(int numDisks) {
  this.numDisks = numDisks;
  source = new Tower(numDisks, "source");
  middle = new Tower(numDisks, "middle");
  destination = new Tower(numDisks, "destination");
  putDisksInInitialTower();
 }

 public void putDisksInInitialTower() {
  for (int i = 0; i < numDisks; i++) {
   source.addDisk((i + 1));
  }
 }

//The idea is if we need to solve tower of Hanoi for N then we can use the solution for N-1
public void solveTOHFor2(Tower source, Tower middle, Tower destination) {
   middle.addDisk(source.removeDiskOnTop());
   destination.addDisk(source.removeDiskOnTop());
   destination.addDisk(middle.removeDiskOnTop());
 }

 public void solveTOHFor3(Tower source, Tower middle, Tower destination) {
  solveTOHFor2(source, destination, middle);
  destination.addDisk(source.removeDiskOnTop());
  solveTOHFor2(middle, source, destination);
 }

 public void solveTOHFor4(Tower source, Tower middle, Tower destination) {
  solveTOHFor3(source, destination, middle);
  destination.addDisk(source.removeDiskOnTop());
  solveTOHFor3(middle, source, destination);
 }


 public void solveTOH(int n) {
  System.out.println("SOLVING TOWER OF HANOI!!");
  if(n == 1){
   // we will see later
  }
  else if(n == 2){
   solveTOHFor2(source, middle, destination);
  }
  else if(n == 3){
   solveTOHFor3(source, middle, destination);
  }
  else if(n == 4 ){
   solveTOHFor4(source, middle, destination);
  }else{
  // a general approach for solving number of disks = n we will see later
  }
 }
 public void printDisksOnTower() {
  source.print();
  middle.print();
  destination.print();
 }

 public static void main(String[] args) {
  int numOfDisks = 2;
  TowerOfHanoi toh = new TowerOfHanoi(numOfDisks);
  toh.printDisksOnTower();
  toh.solveTOH(numOfDisks);
  toh.printDisksOnTower();
 }
}

Now lets introduce a method to solve if the number of Disks is 1

public void solveTOHFor1(Tower source, Tower middle, Tower destination) {
  destination.addDisk(source.removeDiskOnTop());
}

Now applying the idea to reuse the solution for n-1 number of disks to solve the problem 

for n disks we can modify the solveTOHFor2() method as below

public void solveTOHFor2(Tower source, Tower middle, Tower destination) {
  solveTOHFor1(source, destination, middle);
  destination.addDisk(source.removeDiskOnTop());
  middle.addDisk(destination.removeDiskOnTop());
}

And Finally we are now in a position to write a recursive method to write a general method for Tower of Hanoi for N disks.

package com.algorithm.recurrsion;

public class TowerOfHanoi {
 public static class Tower {
  int tower[];
  int numDisks;
  int top = -1;
  String name;

  public Tower(int numDisks, String name) {
   this.numDisks = numDisks;
   tower = new int[numDisks];
   this.name = name;
  }

  public void addDisk(int disk) {
   System.out.println("adding   " + disk + " on tower   : " + name);
   tower[++top] = disk;
  }

  public int removeDiskOnTop() {
   int diskOnTop = tower[top];
   System.out.println("removing " + diskOnTop + " from tower : " + name);
   top--;
   return diskOnTop;
  }

  public void print() {
   if (top == -1) {
    System.out.println(name + " Tower is empty");
   } else {
    System.out.print(name + " tower contains... ");
    for (int i = 0; i <= top; i++) {
     System.out.print(tower[i] + " ");
    }
    System.out.println();
   }
  }
 }

 Tower source;
 Tower middle;
 Tower destination;

 int numDisks;

 public TowerOfHanoi(int numDisks) {
  this.numDisks = numDisks;
  source = new Tower(numDisks, "source");
  middle = new Tower(numDisks, "middle");
  destination = new Tower(numDisks, "destination");
  putDisksInInitialTower();
 }

 public void putDisksInInitialTower() {
  for (int i = 0; i < numDisks; i++) {
   source.addDisk((i + 1));
  }
 }

 private void solveTOH(int n, Tower source, Tower middle, Tower destination) {
  if (n >= 1) {
   solveTOH(n - 1, source, destination, middle);
   destination.addDisk(source.removeDiskOnTop());
   solveTOH(n - 1, middle, source, destination);
  }
 }

 public void solveTOH() {
  System.out.println("Solving the tower of Hanoi ...");
  solveTOH(numDisks, source, middle, destination);
 }

 public void printDisksOnTower() {
  source.print();
  middle.print();
  destination.print();
 }

 public static void main(String[] args) {
  int numOfDisks = 6;
  TowerOfHanoi toh = new TowerOfHanoi(numOfDisks);
  toh.printDisksOnTower();
  toh.solveTOH();
  toh.printDisksOnTower();
 }
}