Tower of Hanoi (using stacks)

How can you implement the tower of Hanoi game.

First look at the optimized solution of tower of hanoi.

Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case: (from wikipedia)

For an even number of disks:

make the legal move between pegs A and B
make the legal move between pegs A and C
make the legal move between pegs B and C
repeat until complete

For an odd number of disks:

make the legal move between pegs A and C
make the legal move between pegs A and B
make the legal move between pegs C and B
repeat until complete

In each case, a total of 2n-1 moves are made.

Implemented with stack

public class TowerOfHanoi {
	Stack<Integer> A = new Stack<Integer>();
	Stack<Integer> B = new Stack<Integer>();
	Stack<Integer> C = new Stack<Integer>();
	int diskNum;
	public TowerOfHanoi(int n) {
		for (int i = n; i >= 1; i--) {
			A.push(i);
		}
		diskNum = n;
	}
	
	public int solve() {
		int moves = 0;
		if (diskNum%2 == 1) {// odd number
			while(C.size() != diskNum) {
				if (C.isEmpty() || (!A.isEmpty() && A.peek() < C.peek())) {
					C.push(A.pop());
				}
				else {
					A.push(C.pop());
				}
				moves++;
				if (C.size() == diskNum)
					break;
				if (B.isEmpty() || (!A.isEmpty() && A.peek() < B.peek())) {
					B.push(A.pop());
				}
				else {
					A.push(B.pop());
				}
				moves++;
				if (B.isEmpty() || (!C.isEmpty() && C.peek() < B.peek())) {
					B.push(C.pop());
				}
				else {
					C.push(B.pop());
				}
				moves++;
			}
		}
		else { // even number
			while(C.size() != diskNum) {
				if (B.isEmpty() || (!A.isEmpty() && A.peek() < B.peek())) {
					B.push(A.pop());
				}
				else {
					A.push(B.pop());
				}
				moves++;
				if (C.isEmpty() || (!A.isEmpty() && A.peek() < C.peek())) {
					C.push(A.pop());
				}
				else {
					A.push(C.pop());
				}
				moves++;
				if (C.size() == diskNum)
					break;
				if (B.isEmpty() || (!C.isEmpty() && C.peek() < B.peek())) {
					B.push(C.pop());
				}
				else {
					C.push(B.pop());
				}
				moves++;
			}
		}
		return moves;
	}
	
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s