Tower of Hanoi

How to Play Tower of Hanoi

Tower of Hanoi is a classic recursion puzzle. All the disks begin stacked largest-at-bottom on the left peg. Move the entire stack to the right peg, one disk at a time, following two rules: you may only move the top disk of a peg, and you may never place a larger disk on top of a smaller one. Click a peg to pick up its top disk, then click another peg to drop it. The goal is to rebuild the tower on the right peg in as few moves as possible.

Minimum Moves & the 2^n−1 Formula

The fewest moves needed to solve Tower of Hanoi with n disks is exactly 2ⁿ − 1. Three disks take 7 moves, four disks take 15, and five disks take 31. No sequence can ever beat this bound, so a leaderboard score equal to 2ⁿ − 1 is a perfect, optimal solve.

The Recursive Solution Strategy

• To move n disks from the source peg to the target peg, first move the top n − 1 disks onto the spare (auxiliary) peg.
• Move the single largest disk directly from the source peg to the target peg.
• Finally, move the n − 1 disks from the spare peg on top of the largest disk. Each of those sub-stacks is solved the same way, all the way down to a single disk.

How do you solve Tower of Hanoi in the fewest moves? Apply the recursion above: split the problem into "move n−1 aside, move the biggest, move n−1 back." There is also a simple iterative trick — always move the smallest disk in the same cyclic direction every other move, and make the only other legal move in between — which reproduces the same optimal 2ⁿ − 1 sequence.