The Tower of Hanoi is a puzzle consisting of three poles, on which piles of discs are stacked. The aim is to transfer the pile from the starting pole onto one of the other two, subject to the following restraints:
- Only one disc may be moved at a time, and must be moved from the top of one pile to another
- When moving a disc, it can only be placed on top of a larger one, or onto an empty "pile"
The smallest number of moves in which the puzzle can be completed, for n discs, is 2n – 1
|Tower of Hanoi T|
|Ant on Rod|