Tower of Hanoi

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.

We can denote rods by characters a, b and c. Write a program to move the disks from the first rod to the last using Stacks.

Note that number of moves is equal to 2 ^ n - 1 where n is number of disks.

Other names

The Tower of Hanoi (also called Problem of Benares Temple or Tower of Brahma or Lucas’ Tower and sometimes pluralized as Towers, or simply pyramid puzzle) is a mathematical game or puzzle consisting of three rods or pegs and a number of disks of various diameters, which can slide onto any rod.

Examples

Example 1:

Input: n = 3
Output:
1. Start by moving disk 1 to tower B.
2. Next, transfer disk 2 to tower C.
3. Move disk 1 to tower C.
4. Shift disk 3 to tower B.
5. Move disk 1 back to tower A.
6. Transfer disk 2 to tower B.
7. Finally, move disk 1 to tower B.

Example 2:

Input: n = 4
Output:
1. Move disk 1 from tower A to C.
2. Move disk 2 from tower A to B.
3. Move disk 1 from tower C to B.
4. Move disk 3 from tower A to C.
5. Move disk 1 from tower B to A.
6. Move disk 2 from tower B to C.
7. Move disk 1 from tower A to C.
8. Move disk 4 from tower A to B.
9. Move disk 1 from tower C to B.
10. Move disk 2 from tower C to A.
11. Move disk 1 from tower B to A.
12. Move disk 3 from tower C to B.
13. Move disk 1 from tower A to C.
14. Move disk 2 from tower A to B.
15. Move disk 1 from tower C to B.

If you like to play pause to understand better, please watch below:

Solution

Method 1 - Using Recursion

Here’s an algorithm to move disks from one tower to another using a third tower (refer to the gif at the top for visual understanding):

Move the first two disks from tower A(origin tower) to tower C(destination tower) using tower B(buffer tower or auxiliary tower).
Transfer the last disk from tower A to tower B.
Finally, move the first two disks from tower C to tower B using tower A. And that’s it.

Code

Think of dry run with say n = 4. Here is the output for n = 4:

1[a->c]
2[a->b]
1[c->b]
3[a->c]
1[b->a]
2[b->c]
1[a->c]
4[a->b]
1[c->b]
2[c->a]
1[b->a]
3[c->b]
1[a->c]
2[a->b]
1[c->b]

Java

public void towerOfHanoi(int n, char ta, char tb, char tc) {
	//if we dont have any disks, then just end the function
	if (n == 0) {
		return;
	}

	/*
	now transfer n-1 (3 disks) from tower 1 to tower 3 using tower 2
	 */
	towerOfHanoi(n - 1, ta, tc, tb);

	//now transfer the third (nth) disk from tower a to b
	System.out.println(n + "[" + ta + "->" + tb + "]");

	/*
	now just transfer those n-1 (3 disks) from tower c to tower b
	 */
	towerOfHanoi(n - 1, tc, tb, ta);
}

Complexity

⏰ Time complexity: O(2^n), as at each step we are branching out into 2.
🧺 Space complexity: O(n) assuming recursion stack space

Method 2 - Using Stack but still recursive

We can denote stacks as towers or pegs. Here is the same problem using stack:

If you prefer video, here it is:

Code

Java

public class TowerOfHanoiWithStack {

	private Stack<Integer> [] stacks = new Stack[3];

	private Integer[] disks;

	public TowerOfHanoiWithStack(int n) {
		stacks[0] = new Stack<Integer>();
		stacks[1] = new Stack<Integer>();
		stacks[2] = new Stack<Integer>();
		disks = new Integer[n];

		for (int i = 1; i <= n; i++) {
			stacks[0].push(i);
		}
	}

	public void solve() {
		solveRecursively(0, 2, 1, disks);
	}

	private void solveRecursively(int srcIdx, int destIdx, int auxIdx) {
		Stack<Integer> srcStk = stacks[srcIdx];
		Stack<Integer> destStk = stacks[destIdx];

		// Move n-1 disks from src to aux, so they are out of the way
		solveRecursively(n - 1, srcIdx, auxIdx, destIdx);
		Integer disk = srcStk.pop();
		destStk.push(disk);
		System.out.println("Move " + disk + " from " + srcIdx + " to " + destIdx);

		if (disks.length > 1) {
			subDisks = new Integer[disks.length - 1];
			System.arraycopy(disks, 0, subDisks, 0, disks.length - 1);
			solveRecursively(srcIdx, auxIdx, destIdx, subDisks);
		}

		// Move the n-1 disks from aux to dest
		solveRecursively(n - 1, auxIdx, destIdx, srcIdx);
	}
}

Complexity

⏰ Time complexity: O(2^n)
🧺 Space complexity: O(n) using both recursive and actual stacks.

Method 3 - Iterative making move object

Here’s an iterative approach to solve the Tower of Hanoi problem using a stack in Java:

Use a class to represent a move in the stack.
Simulate the recursive behavior of the Tower of Hanoi algorithm using an explicit stack.

Here is the explanation:

Move Class: Represents a move and contains disk information and source (from), destination (to), auxiliary tower (aux), and a boolean (isBaseCase) to indicate if it’s a base case (direct move of the disk).
Initialization: Push the initial move onto the stack.
Iteration:
- While the stack is not empty, pop a move from the stack.
- If the disk is 0, simply continue (base case termination).
- If it’s a base case, print the move.
- Otherwise, simulate the recursive behavior by pushing the appropriate moves onto the stack to follow these steps:
  - Move n-1 disks from the auxiliary tower to the destination tower using the source tower.
  - Move the nth disk from the source tower to the destination tower.
  - Move n-1 disks from the source tower to the auxiliary tower using the destination tower.

The solution uses a stack to simulate recursive calls iteratively, following the principles of the Tower of Hanoi problem. The main loop keeps executing until all moves are processed. This approach eliminates the need for recursion by manually managing the function call stack.

Code

Java

class Move {
	int disk;
	char from;
	char to;
	char aux;
	boolean isBaseCase;

	Move(int disk, char from, char to, char aux, boolean isBaseCase) {
		this.disk = disk;
		this.from = from;
		this.to = to;
		this.aux = aux;
		this.isBaseCase = isBaseCase;
	}
}


public class TowerOfHanoi {

	public void towerOfHanoi(int n, char ta, char tb, char tc) {
		Stack<Move> stack = new Stack<>();

		// Push the initial move to the stack
		stack.push(new Move(n, ta, tb, tc, false));

		while (!stack.isEmpty()) {
			Move move = stack.pop();

			if (move.disk == 0) {
				continue;
			}

			if (move.isBaseCase) {
				System.out.println(move.disk + "[" + move.from + "->" + move.to + "]");
			} else {
				// Perform the sequence of moves in reverse order
				stack.push(new Move(move.disk - 1, move.aux, move.to, move.from, false)); // Move n-1 disks from aux to to using from as auxiliary
				stack.push(new Move(move.disk, move.from, move.to, move.aux, true)); // Move nth disk from from to to
				stack.push(new Move(move.disk - 1, move.from, move.aux, move.to, false)); // Move n-1 disks from from to aux using to as auxiliary
			}
		}
	}

	public static void main(String[] args) {
		TowerOfHanoi toh = new TowerOfHanoi();
		int n = 3; // Number of disks
		toh.towerOfHanoi(n, 'A', 'B', 'C'); // A, B, and C are names of the three towers
	}
}

Complexity

⏰ Time complexity: O(2^n)
🧺 Space complexity: O(n)

Problem#

Other names#

Examples#

Solution#

Method 1 - Using Recursion#

Code#

Java#

Complexity#

Method 2 - Using Stack but still recursive#

Code#

Java#

Complexity#

Method 3 - Iterative making move object#

Code#

Java#

Complexity#

Problem

Other names

Examples

Solution

Method 1 - Using Recursion

Code

Java

Complexity

Method 2 - Using Stack but still recursive

Code

Java

Complexity

Method 3 - Iterative making move object

Code

Java

Complexity