Tower Of Hanoi

What is the Tower of Hanoi?

Tower of Hanoi is a classic mathematical puzzle that involves moving a stack of disks from one peg to another, following a specific set of rules. It was invented by French mathematician Édouard Lucas in 1883. The puzzle is often used to teach recursive algorithms in computer science.

How to Play the Game

You are given:

• Three pegs (rods)

• Several disks of different sizes stacked in decreasing order (largest at the bottom, smallest on top) on one peg

Objective:

Move the entire stack to another peg, obeying the following rules:

• Only one disk can be moved at a time

• Only the top disk of any stack can be moved

• No larger disk may be placed on top of a smaller disk

Basic Gameplay

• Start with all disks stacked in order on the first peg.

• Use the second peg as a helper or temporary holding area.

• Transfer disks to the third peg, keeping the order intact.

• The puzzle gets more complex as the number of disks increases.

Example with 3 disks:

• Move disk 1 → Peg 3

• Move disk 2 → Peg 2

• Move disk 1 → Peg 2

• Move disk 3 → Peg 3

• Move disk 1 → Peg 1

• Move disk 2 → Peg 3

• Move disk 1 → Peg 3

Minimum moves required = 2n−12^n - 12n−1 where n is the number of disks.