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

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.

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);
        }
    }
}

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
        }
    }
}

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)