The Tower of Hanoi is a classic mathematical puzzle and problem-solving exercise that involves moving a stack of disks from one peg to another, following specific rules. The puzzle consists of three pegs and a number of disks of different sizes that can slide onto any peg. The objective is to move the entire stack of disks from the source peg to a target peg while adhering to the following rules: 1. Only one disk can be moved at a time.
Articles by others on the same topic
The Tower of Hanoi has three pegs and differently sized discs. Start with all discs stacked largest below smallest on one peg; move one exposed disc at a time, never placing a larger disc on a smaller one, and transfer the stack to another peg.
To move the largest disc, the upper discs must first be collected on the third peg. After its move they must be transferred again. Hence the minimum satisfies , , giving . The recursive construction attains this lower bound. The problem shows how a short recursive procedure can require exponentially many executed moves.