Tower of Hanoi: A Beginner's Guide 🎯

Welcome to CodeYourCraft, where we help you learn programming concepts from scratch! Today, we're diving into the fascinating world of Data Structures and Algorithms, starting with the classic puzzle game: Tower of Hanoi.

What is Tower of Hanoi? 📝

Tower of Hanoi is a simple, yet challenging puzzle game. It involves three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, and the objective is to move the entire stack to another rod, obeying a simple set of rules.

The Rules 💡

Only one disk can be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or an empty rod.
No disk may be placed on top of a smaller disk.

The Optimal Solution ✅

The minimum number of moves required to solve the Tower of Hanoi is 2^N - 1, where N is the number of disks. This is an interesting property and forms the basis of its use in various algorithms.

Let's Solve a Tower of Hanoi Puzzle 💡

Let's consider a puzzle with 3 disks.

markdown

   A |   B |     C
-------------------
1 | 2 | 3  (Disks sizes)

We need to move the entire stack from rod A to rod C. Here's how we can do it:

Move disk 1 from rod A to rod C.
markdown
A | B | C

. | 2 | 3 (Disks sizes) 1 | | C


2. Move disk 2 from rod B to rod A.
   ```markdown
   A |   B |     C
-------------------
2 | . | 3  (Disks sizes)
1 |      | C

Move disk 1 from rod C to rod B.
markdown
A | B | C

2 | 1 | 3 (Disks sizes) | | C


4. Move disk 3 from rod C to rod A.
   ```markdown
   A |   B |     C
-------------------
2 | 1 | .  (Disks sizes)
3 |      | A

Move disk 1 from rod B to rod C.
markdown
A | B | C

2 | | C 1 | | A 3 | | .


6. Move disk 2 from rod A to rod C.
   ```markdown
   A |   B |     C
-------------------
      | 2 | C
1 |      | A
3 |      | .

Finally, move disk 1 from rod B to rod C.
markdown
A | B | C

  | 2 | C
  | 1 | A

3 | | .


And there you have it! The entire stack has been moved from rod A to rod C.

## Solving Tower of Hanoi Programmatically 💡

Now, let's implement a simple Python program to solve the Tower of Hanoi for any number of disks.

```python
def hanoi(n, source, target, auxiliary):
    if n > 0:
        # Move n - 1 disks from source to auxiliary
        hanoi(n - 1, source, auxiliary, target)

        # Move the nth disk from source to target
        print(f"Move disk {n} from rod {source} to rod {target}")

        # Move the (n - 1) disks that we left on auxiliary to target
        hanoi(n - 1, auxiliary, target, source)

# Driver code
hanoi(3, 'A', 'C', 'B')

This program follows the same logic as our manual solution, but for any number of disks!

Quiz Time 🎯

That's all for today! We hope you enjoyed learning about the Tower of Hanoi. Stay tuned for more exciting lessons on Data Structures and Algorithms at CodeYourCraft! 🎉