Thursday, April 17, 2014

Solve Towers of Hanoi using stack

Problem

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.  

Solution

Let us denote the three rods, from left to right, as src, transfer and des.
  • 1 disk only: move from src to des. done.
  • 2 disks(top to bottom: 1->2): move 1 from src to transfer, move 2 from src to des, move 1 from transfer to des.
  • 3 disks: ‘magically(recursively)’ move {1,2} from src to transfer, move 3 from src to des, ‘magically(recursively)’ move {1,2} from transfer to des.
  • n disks: recursively move the top n-1 disks from src to transfer, move n from src to des, recursively move the n-1 disks from transfer to des.
 For n disks, we need 2^n-1 steps at minimum to finish the game.
public class TowerOfHanoiWithStack {
 
    private Stack<Object>[] stacks = new Stack[3];
    private Object[] disks;
 
    public TowerOfHanoiWithStack(Object[] disks) {
        stacks[0] = new Stack<Object>();
        stacks[1] = new Stack<Object>();
        stacks[2] = new Stack<Object>();
        this.disks = disks;
        for (Object o : disks)
            stacks[0].push(o);
    }
 
    public void solve() {
        solveRecursively(0, 2, 1, disks);
    }
 
    public void solveRecursively(int sourceIndex, int desIndex,
            int transferIndex, Object[] disks) {
        Stack<Object> source = stacks[sourceIndex];
        Stack<Object> des = stacks[desIndex];
 
        Object[] sub_disks = null;
        if (disks.length > 1) {
            sub_disks = new Object[disks.length - 1];
            System.arraycopy(disks, 0, sub_disks, 0,
                    disks.length - 1);
            solveRecursively(sourceIndex, transferIndex,
                    desIndex, sub_disks);
        }
        Object t = source.pop();
        des.push(t);
        System.out.println("Move " + t + " from " +
                sourceIndex + " to " + desIndex);
 
        if (disks.length > 1)
            solveRecursively(transferIndex, desIndex,
                    sourceIndex, sub_disks);
    }
}

References

Reactions:

0 comments:

Post a Comment