Tower of Hanoi in Data Structure

Tower of Hanoi is a classic mathematical puzzle involving three rods and a number of disks of different sizes. The objective is to move the entire stack of disks from the source rod to a destination rod, following specific rules, using an auxiliary rod.

Rules

• Only one disk can be moved at a time.
• Each move takes the top disk from one stack and places it on top of another stack or an empty rod.
• A larger disk may never be placed on top of a smaller disk.

Recursive Solution

To move n disks from the source rod to the destination rod: move the top n-1 disks from source to the auxiliary rod, move the nth (largest) disk from source to destination, then move the n-1 disks from the auxiliary rod to the destination rod.

def tower_of_hanoi(n, source, auxiliary, destination):
    if n == 0:
        return
    tower_of_hanoi(n - 1, source, destination, auxiliary)
    print(f"Move disk {n} from {source} to {destination}")
    tower_of_hanoi(n - 1, auxiliary, source, destination)

tower_of_hanoi(3, 'A', 'B', 'C')

Complexity

The minimum number of moves required to solve the puzzle for n disks is exactly 2^n − 1.

Applications

• A classic teaching example for understanding recursion and recurrence relations.
• Used to illustrate backup rotation schemes (Tower of Hanoi backup rotation in data storage).
• Basis for algorithmic problems involving state-space search and puzzle solving.