Tower of Hanoi

How to play the Tower of Hanoi

• The Tower of Hanoi is a puzzle with three pegs and a stack of disks. Move the whole stack from the left peg to the right peg.
• Move one disk at a time, and only the top disk of a peg. A larger disk can never go on top of a smaller one.
• Tap the peg with the disk you want to move, then tap the peg to move it to. You can also drag a disk. On a computer, the 1, 2 and 3 keys pick the left, middle and right pegs, and Ctrl+Z undoes a move.
• Choose from 3 to 10 disks. New to the puzzle? Start with 3 or 4 disks, and add one more each time you solve it in the fewest moves.
• The daily puzzle is one puzzle a day, the same for everyone: five disks scattered across the three pegs. Move them all to the right peg. The minimum number of moves changes from day to day. A new puzzle comes out every day at 15:00 UTC. Hints still count as a clear, but seeing the solution doesn’t.
• Stuck? “Hint” lights up the next move of the shortest solution from where you are. “Solve” moves the disks for you along the shortest solution (tap it again to stop). Rounds with hints or Solve don’t count toward your personal best. If you close the page, your game is saved so you can pick up where you left off.

Minimum number of moves

With n disks, the minimum number of moves is 2ⁿ − 1 (2 multiplied by itself n times, minus 1). Each extra disk roughly doubles the number of moves.

Why? Look at the largest disk. Before it can move to the right peg, all n − 1 disks above it have to be out of the way on the middle peg. Then the largest disk moves to the right in one move, and the n − 1 disks go back on top of it. So n disks take “moves for n − 1 disks × 2 + 1”: 3 disks take 3 × 2 + 1 = 7 moves, 4 disks take 7 × 2 + 1 = 15 moves, and so on.

How to solve the Tower of Hanoi

• Move the smallest disk every other turn, always around in the same direction. With an odd number of disks (3, 5, 7, 9), it goes left → right → middle → left…; with an even number (4, 6, 8, 10), left → middle → right → left…
• On the other turns, there is only one move you can make. Between the two pegs without the smallest disk, move the smaller top disk onto the other peg (or onto the empty one).
• Repeat these two steps and you will solve any number of disks in the fewest moves. If you get lost, think of the top n − 1 disks as one block: move the block to the middle, move the largest disk to the right, then move the block on top of it.

The recursive solution

The block idea is the classic example of recursion in programming. To move n disks, move n − 1 disks to the spare peg, move the largest disk, then move the n − 1 disks onto it:

function hanoi(n, from, to, spare) {
  if (n === 0) return;
  hanoi(n - 1, from, spare, to);
  move(from, to);
  hanoi(n - 1, spare, to, from);
}

About the Tower of Hanoi

The Tower of Hanoi was invented by the French mathematician Édouard Lucas and first presented in 1883, as a game supposedly found by “N. Claus de Siam” (an anagram of Lucas d’Amiens). It came with a legend: in a temple in Benares, priests are moving the 64 golden disks of the Tower of Brahma, and when they finish, the world will end. Moving 64 disks takes at least 18,446,744,073,709,551,615 moves. At one move per second, that is about 585 billion years. Today the puzzle is a favorite in math and programming classes, and psychologists use it to study problem solving.