# Towers Of Hanoi

In the classic problem of the Towers of Hanoi, you have 3 towers 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 (Le., each disk sits on top of an even larger one). You have the following constraints:

(1) Only one disk can be moved at a time.

(2) A disk is slid off the top of one tower onto another tower.

(3) A disk cannot be placed on top of a smaller disk.

Write a program to move the disks from the first tower to the last using stacks.

## Link here to the repo to solve the problem

👉## 👌 Tips

Try the Base Case and Build approach.

You can easily move the smallest disk from one tower to another. It's also pretty easy to move the smallest two disks from one tower to another. Can you move the smallest three disks?

Think about moving the smallest disk from tower X=0 to tower Y=2 using tower Z = 1 as a temporary holding spot as having a solution for f(1, X=0, Y=2, Z=1). Moving the smallest two disks is f(2, X=0, Y=2, Z=l).Given that you have a solution for f(1, X=0, Y=2, Z=1) and f(2, X=0, Y=2, Z=1), can you solve f(3, X=0, Y=2, Z=1)?

Observe that it doesn't really matter which tower is the source, destination, or buffer. You can do f(3, X=0, Y=2, Z=l) by first doing f(2, X=0, Y=l, Z=2) (moving two disks from tower 0 to tower 1, using tower 2 as a buffer), then moving disk 3 from tower 0 to tower 2,then doing f(2, X=l, Y=2, Z=0) (moving two disks from tower 1 to tower 2, using tower 0 as a buffer). How does this process repeat?

If you're having trouble with recursion, then try trusting the recursive process more. Once you've figured out how to move the top two disks from tower 0 to tower 2, trust that you have this working. When you need to move three disks, trust that you can move two disks from one tower to another. Now, two disks have been moved.What do you do about the third?

## 👊 Solution 1

**Moving the disk 1 step looks like:**

Let's start with the smallest possible example: n 1.

Casen = 1. Can we move Disk 1 from Tower 1 to Tower 3? Yes.

- We simply move Disk 1 from Tower 1 to Tower 3.

Case n = 2. Can we move Disk1 and Disk2 from Tower 1 to Tower 3? Yes.

- Move Disk 1 from Tower 1 to Tower 2
- Move Disk 2 from Tower 1 to Tower 3
- Move Disk 1 from Tower 2 to Tower 3

Note how in the above steps, Tower 2 acts as a buffer, holding a disk while we move other disks to Tower 3.

Case n = 3. Can we move Disk 1,2, and 3 from Tower 1 to Tower 3? Yes.

- We know we can move the top two disks from one tower to another (as shown earlier), so let's assume we've already done that. But instead, let's move them to Tower 2.
- Move Disk 3 to Tower 3.
- Move Disk 1 and Disk 2 to Tower 3. We already know how to do this-just repeat what we did in Step 1.

Casen = 4. Can we move Disk 1, 2, 3 and 4 from Tower 1 to Tower 3? Yes.

- Move Disks 1,2, and 3to Tower 2. We know how to do that from the earlier examples.
- Move Disk 4 to Tower 3.
- Move Disks 1,2 and 3 back to Tower 3.

Remember that the labels ofTower 2 and Tower 3 aren't important. They're equivalent towers. So, moving disks to Tower 3 with Tower 2 serving as a buffer is equivalent to moving disks to Tower 2 with Tower 3 serving as a buffer.

This approach leads to a natural recursive algorithm. In each part, we are doing the following steps, outlined below with pseudocode:

```
moveDisks(int n, Tower origin, Tower destination, Tower buffer) {
if(n <= 0) return;
/* move top n - 1 disks from orIgIn to buffer, using destination as a buffer. */
moveDisks(n - 1, origin, buffer, destination);
/* move top from origin to destination */
moveTop(origin, destination);
/* move top n - 1 disks from buffer to destination, using origin as a buffer. */
moveDisks(n - 1, buffer, destination, origin);
}
```

Here is the code in Java:

```
public class TowersOfHanoi {
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[2], towers[1]);
}
private static class Tower {
private Stack<Integer> disks;
private int index;
public Tower(int i) {
disks = new Stack<>();
index = i;
}
public void add(int d) {
if(!disks.isEmpty() && disks.peek() <= d) System.out.println("error moving disk: " + d);
else disks.push(d);
}
public void moveTopTo(Tower t) {
int top = disks.pop();
t.add(top);
}
public int getIndex() {
return index;
}
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);
}
}
}
}
```

*Question and solution borrowed from “Cracking the coding interview”*