Recursive Algorithm in C# Using Towers of Honoi

Introduction

The Tower of Hanoi, also known as the "Towers of Hanoi" or "Tower of Brahma," is a classic puzzle that has fascinated mathematicians, computer scientists, and puzzle enthusiasts for over a century. It was first introduced by French mathematician Édouard Lucas in 1883. The puzzle consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks neatly stacked in ascending order of size on one rod, the largest disk on the bottom, and the smallest at the top. The objective is to move the entire stack to another rod, following certain rules.

Rules of the Game

Only one disk can be moved at a time: You can only take the top disk from one of the stacks and place it on another rod.

A disk can only be placed on top of a larger disk or an empty rod: This means you cannot place a larger disk on top of a smaller disk.

The challenge is to move the stack of disks from the source rod to the target rod, using the third rod as an auxiliary, with the minimum number of moves. The minimum number of moves required to solve the puzzle is 2n−12^n - 1, where nn is the number of disks.

Solving the Tower of Hanoi

The Tower of Hanoi puzzle can be solved using a recursive algorithm. The idea is to break down the problem into smaller subproblems until the base case is reached. Here is a step-by-step approach:

• Move the top n−1n-1 disks from the source rod to the auxiliary rod.
• Move the nn-th (largest) disk from the source rod to the target rod.
• Move the n−1n-1 disks from the auxiliary rod to the target rod.

Sample Code Snippet

Below is a sample implementation of the Tower of Hanoi puzzle in C#:

using System;

class TowerOfHanoi
{
    static void Main(string[] args)
    {
        int n = 3; // Number of disks
        SolveTowerOfHanoi(n, 'A', 'C', 'B');
    }

    static void SolveTowerOfHanoi(int n, char source, char target, char auxiliary)
    {
        if (n == 1)
        {
            Console.WriteLine($"Move disk 1 from {source} to {target}");
            return;
        }

        SolveTowerOfHanoi(n - 1, source, auxiliary, target);
        Console.WriteLine($"Move disk {n} from {source} to {target}");
        SolveTowerOfHanoi(n - 1, auxiliary, target, source);
    }
}

Explanation of the Code

1. Main Method: The Main method initializes the number of disks and calls the SolveTowerOfHanoi method.
2. SolveTowerOfHanoi Method: This is a recursive method that takes the number of disks n, the source rod, the target rod, and the auxiliary rod as parameters. It solves the puzzle by breaking it down into smaller subproblems:
   • Base Case: If there is only one disk, move it directly from the source rod to the target rod.
   • Recursive Case:
     Move the top n−1n-1 disks from the source rod to the auxiliary rod.
     Move the nn-th disk from the source rod to the target rod.
     Move the n−1n-1 disks from the auxiliary rod to the target rod.

Sample Output

The sample output for n=3n = 3 disks would be:

Conclusion

The Tower of Hanoi is a fascinating puzzle that not only provides an engaging challenge but also offers valuable lessons in recursion and algorithm design. By understanding the rules and recursive approach, you can solve the puzzle efficiently. The sample code and output provided in this article illustrate the process of solving the Tower of Hanoi puzzle for any number of disks using a recursive algorithm in C#.