No. 4 - Towers Of Hanoi

Back to Menu

Problem:

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

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.

Solution:

Suppose we are moving discs from tower 1 to tower 2 with the help of tower 3. We can see that the bigger disc of the bottom can only be moved when all top discs are moved out of tower 1. As this is the bigger disc it can only go to an empty rod. So this creates a subproblem. To move all the disc from 1 to 2, we need to move n-1 discs from 1 to 3 using 2. Now after moving the top n-1, we can move the bottom one to tower2 as it is empty at that point. After that we need to move all discs from tower 3 to tower 2 with the help of tower 1, as this is currently empty.

Example

TowersOfHanoi.java

package com.meritmix.blog.algo;
import java.util.Stack;
/**
 * @author Ravi Yadav
 * This is copyright content of MeritMix.com
 * blog address is blog.meritmix.com 
 */
public class TowersOfHanoi{
 public static void main(String[] args) {
  Tower source = new Tower("1");
  Tower destination = new Tower("2");
  Tower aux = new Tower("3");
  source.push(4);
  source.push(3);
  source.push(2);
  source.push(1);
  move(source.size(), source, destination, aux);
 }

 private static void move(int size, Tower source, Tower destination,
   Tower aux) {
  if (source.isEmpty())
   return;
  if (size == 1) {
   System.out.println("Move " + source.peek() + " from tower "
     + source.name + " to tower " + destination.name);
   destination.push(source.pop());
   return;
  }
  move(size - 1, source, aux, destination);
  move(1, source, destination, aux);
  move(size - 1, aux, destination, source);
 }

 private static class Tower {
  public String name;
  private Stack<Integer> stack = new Stack<Integer>();

  public Tower(String name) {
   this.name = name;
  }

  public int pop() {
   return stack.pop();
  }

  public int peek() {
   return stack.peek();
  }

  public boolean isEmpty() {
   return stack.isEmpty();
  }

  public int size() {
   return stack.size();
  }

  public void push(int i) {
   stack.push(i);

  }
 }
}

Back to Menu