Wednesday, February 25, 2015

Hanoi Game

In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower.The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one).You have the following constraints:
(A) Only one disk can be moved at a time.
(B) A disk is slid off the top of one rod onto the next rod.
(C) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first rod to the last using Stacks.


Consider the easiest problem, if we have 2 disks, how should we move from Tower 0 to Tower 2? See the following illustration:


Now what if we have 3 disks? So in the end we want to move all 3 disks to Tower 2, we would have to move disk0 and disk1 to Tower 1 first, because disk2 will be at the bottom of Tower 2, so we need to leave the space for it. 


Yes, we will use recursion to solve the problem. 


import java.util.Stack;
public class HanoiGame {
 private Stack disks;
 private int index;
 public HanoiGame(int i) {
  disks = new Stack();
  index = i;
 }
 /**
  * tower id
  * @return
  */
 public int index() {
  return index;
 }
 /**
  * add disk with length d to the tower
  * if the last disk on the top of the tower is smaller
  * than d, then d cannot be added to the tower
  * @param d
  * @return
  */
 public boolean add(int d) {
  if (!disks.isEmpty() && disks.peek() <= d) {
   System.out.println("Error placing disk: " + d);
   return false;
  }
  else
   disks.push(d);
  return true;
 }
 /**
  * move the top disk to the desired tower
  * @param hg
  */
 public void moveTopTo(HanoiGame tower) {
  int top = disks.pop();
  if (!tower.add(top))
   disks.push(top);
  //System.out.println("Move disk " + top + " from " + index() 
   // + " to " + tower.index());
 }
 public void print() {
  System.out.println("Contents of Tower: " + index());
  for (int i = disks.size() - 1; i >= 0; i--) {
   System.out.println(disks.get(i) + " ");
  }
 }
 /**
  * move the disks to the destination
  * use recursion to solve the problem
  * @param n
  * @param destination
  * @param intermediate
  */
 public void moveDisks(int n, HanoiGame destination, HanoiGame intermediate) {
  if (n > 0) {
   //since the last disk must be placed at the destination
   //we need to move n - 1 disks above it to the intermediate first
   moveDisks(n - 1, intermediate, destination);
   //move the last disk to the destination
   moveTopTo(destination);
   //from intermediate move the n - 1 disks to the destination, 
   //using current tower as the new intermediate
   intermediate.moveDisks(n - 1, destination, this);
  }
 }
 public static void main(String[] args) {
  int n = 5;
  HanoiGame[] towers = new HanoiGame[3];
  for (int i = 0; i < 3; i++)
   towers[i] = new HanoiGame(i);
  for (int i = n - 1; i >= 0; i--)
   towers[0].add(i);
  towers[0].print();
  towers[0].moveDisks(n, towers[2], towers[1]);
  towers[2].print();
 }

}

No comments:

Post a Comment