Minesweeper
Brain Teasers Play now
The Tower of Hanoi is a mathematical puzzle invented by French mathematician Édouard Lucas in 1883. You win by moving a pyramid of disks from one of three pegs to another, one disk at a time, never putting a larger disk on a smaller one.
All disks start stacked on one peg in order, largest at the bottom and smallest on top. There are three pegs, and the goal is to rebuild the same stack on a different peg.
You move one disk per turn, and only the top disk of a peg. A disk can go on an empty peg or on top of a larger disk, but never on top of a smaller one.
The puzzle is solved when the whole tower sits on the target peg in the correct size order. The minimum number of moves for n disks is exactly 2ⁿ − 1.
To move n disks, first move the top n−1 to the spare peg, move the largest disk to the goal, then move the n−1 stack on top of it. Every solution is this pattern nested inside itself.
The smallest disk moves every other turn and always travels in the same direction around the three pegs. Keep it cycling, and fill the turns in between with the only other legal move.
On turns when you don't move the smallest disk, exactly one legal move exists between the other two pegs. Make it. There's never any guessing.
With an even number of disks, move the smallest disk to the spare peg first. With an odd number, move it straight to the target peg. The right first direction guarantees the minimum-move solution.
For n disks the minimum is 2ⁿ − 1 moves. Three disks take 7 moves, four take 15, and ten disks take 1,023.
At one move per second, 2⁶⁴ − 1 moves would take about 585 billion years. That's the number behind the legend of the priests of Brahma moving a 64-disk tower.
Yes. The four-peg version is called the Reve's puzzle. It uses the Frame–Stewart algorithm and needs far fewer moves than the three-peg version.
Yes. Move the smallest disk in one consistent direction every other turn, and make the single other legal move in between. That produces the optimal solution.