tower of hanoi using stacks - Empty Stack Exception

Question

I am a programming novice. Basically I am trying to implement a Tower of Hanoi using stacks. I referred to Cracking the Code Interview solutions and it seems to have a empty stack exception error. I re-wrote the recursion part but still get this error. Why am I getting this error?

import java.util.*;

public class Tower {

    private Stack<Integer> disks;
    private int index;
    public Tower(int i) {
        disks = new Stack<Integer>();
        index = i;
    }

    public int index() {
        return index;
    }

    public void add(int d) {
        if(!disks.isEmpty() && disks.peek() <= d) {
            System.out.println("Error placing disk: " + d);
        }
        else {
            disks.push(d);
        }
    }

    public void moveTopTo(Tower t) {
        int top = disks.pop();
        t.add(top);
        System.out.println("Move disk " + top
                           + " from " + index() + " to " + t.index());
    }

    public void moveDisks(int n, Tower origin, Tower buffer, Tower destination) {
        if(n == 1) {
            moveTopTo(destination);
        }
        else if(n > 0) {
            moveDisks(n - 1, origin, destination, buffer);
            moveTopTo(destination);
            moveDisks(n - 1, buffer, origin, buffer);
        }
    }

    public static void main(String[] args) {
        int n = 3;
        Tower[] towers = new Tower[n];
        for(int i = 0; i < 3; i++) {
            towers[i] = new Tower(i);
        }
        for(int i = n - 1; i >= 0; i--) {
            towers[0].add(i);
        }
        towers[0].moveDisks(n, towers[0], towers[1], towers[2]);
    }
}

Answer 1

Looks like you're treating moveDisks() as if it were static: it's taking three tower parameters. In other words, it isn't really an instance method of a particular tower at all.

But the problem is that within that code, you call .moveToTop(), and that certainly is an instance method: it moves a disk from this particular tower.

As a first try towards a solution, I'd try going back to the book solution, but changing it just a little:

public void moveDisks(int n, Tower destination, Tower buffer) {
    if(n > 0) {
        moveDisks(n - 1, buffer, destination);
        moveTopTo(destination);
        buffer.moveDisks(n - 1, destination, this);
    }
}

The last line is the key. We're saying:

1. Move n-1 disks from this tower to the buffer, using the destination as a buffer.
2. Move the top disk from this tower to the destination.
3. (The key bit) move n-1 disks from the buffer to the destination, using this tower as a buffer.

---

The alternative is to get your approach working. If you want to do that, start by declaring your .moveDisks() as static. Once you've done so, the compiler will complain about the .moveToTop() call, which also needs to be made static. And when you've made that static too, you'll find that you need to pass it two towers: a source and a destination.

---

At the moment, you have a mixture of the two approaches, which is why it's going wrong.