Tower of Hanoi Game: Play the Puzzle Online, Solution and Formula

How to play the Tower of Hanoi: the rules

1. The tower starts on the first peg, the largest disk at the bottom and the smallest at the top.
2. Move one disk at a time: the top disk of one peg onto another peg.
3. A disk can go on an empty peg or on a larger disk, never on a smaller one.
4. The puzzle is solved when the whole tower stands on the last peg, in the same order.

The Tower of Hanoi formula: the minimum number of moves

A tower of n disks needs at least 2ⁿ − 1 moves. Each disk more doubles the moves, and one more.

• 73 disks
• 154 disks
• 315 disks
• 636 disks
• 1277 disks
• 2558 disks

The Tower of Hanoi algorithm

The classic example of recursion: to move n disks, move n − 1 disks to the spare peg, move the largest disk, then move the n − 1 disks onto it. A tower of 0 disks needs no move, which ends it. In Python:

def hanoi(n, source="A", target="C", spare="B"):
    if n == 0:
        return
    hanoi(n - 1, source, spare, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, spare, target, source)

hanoi(4)  # 15 moves

Each call makes two calls on one disk fewer, so the moves follow M(n) = 2 M(n − 1) + 1, with M(1) = 1: the formula 2ⁿ − 1.

The history and the legend

The French mathematician Édouard Lucas published the puzzle in 1883 as a toy, under the name N. Claus de Siam, an anagram of Lucas d'Amiens. It came with a legend: in a temple, priests move a tower of 64 golden disks by the same rules, and when they finish, the world will end.