# 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 (i.e., each disk sits on top of an even larger one). You have the following constraints:

* Only one disk can be moved at a time.
* A disk is slid off the top of one tower onto another tower.
* 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.

### Solutions

![image](https://github.com/VikashChauhan51/algorithms/assets/14816038/c523f09b-b387-4281-9036-f4551e615064)

Let's start with the smallest possible example: n = 1. Case n = 1. Can we move Disk 1 from Tower 1 to Tower 3? Yes.

#### Approach 1 – Using Recursion

***

**Steps**

1. We simply move Disk 1 from Tower 1 to Tower 3. Case n = 2. Can we move Disk 1 and Disk 2 from Tower 1 to Tower 3? Yes.
2. Move Disk 1 from Tower 1 to Tower 2
3. Move Disk 2 from Tower 1 to Tower 3
4. 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.

1. 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.
2. Move Disk 3 to Tower 3.
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.

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

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

Remember that the labels of Tower 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.

```csharp
public class Tower
{
    private Stack<int> disks;
    public string Name { get; private set; }

    public Tower(string name)
    {
        disks = new Stack<int>();
        Name = name;
    }

    public void Push(int disk)
    {
        if (disks.Count == 0 || disks.Peek() >= disk)
        {
            disks.Push(disk);
        }

    }

    public int Pop()
    {
        return disks.Pop();
    }

    public void PrintTower()
    {
        foreach (int disk in disks)
        {
            Console.WriteLine(disk);
        }
    }
}
```

```csharp
public class TowersOfHanoi
{

    public static void MoveDisks(int n, Tower source, Tower destination, Tower auxiliary)
    {
        if (n > 0)
        {
            MoveDisks(n - 1, source, auxiliary, destination); // Move n-1 disks from source to auxiliary tower
            int disk = source.Pop(); // Move the nth disk from source to destination tower
            destination.Push(disk);
            MoveDisks(n - 1, auxiliary, destination, source); // Move the n-1 disks from auxiliary to destination tower
        }
    }
}
```

```csharp
public class Program
{
    static void Main()
    {
        int numDisks = 3; // Number of disks to be moved
        Tower source = new Tower("Source");
        Tower destination = new Tower("Destination");
        Tower auxiliary = new Tower("Auxiliary");

        // Initializing the source tower with disks in ascending order
        for (int i = numDisks; i > 0; i--)
        {
            source.Push(i);
        }

        TowersOfHanoi.MoveDisks(numDisks, source, destination, auxiliary);

        // Print the final arrangement of disks on the destination tower
        Console.WriteLine("Disks on the destination tower:");
        destination.PrintTower();

        Console.ReadLine();
    }
}
```

**Time Complexity:** O(2^N)) 2 power N

**Auxiliary Space:** O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs-57.gitbook.io/data-structure-and-algorithms/problems/backtracking/towers-of-hanoi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.