Solve Towers of Hanoi using stack

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.

My initial thoughts:
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.

My codes:(solution)

import java.util.Stack;
public class Q3_4 {

	private Stack<Object>[] stacks = new Stack[3];
	private Object[] disks;

	public Q3_4(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);
	}
}
Advertisements

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

%d bloggers like this: