IIF Certified Assessment
Start IQ Test
IIF Certified Assessment
Brain Games · Planning
Move the tower from peg A to peg C, one disk at a time, never a larger disk on a smaller one. 7 moves is the minimum.
In short
The Tower of Hanoi is a puzzle with three pegs and a stack of disks, largest at the bottom. You move the whole tower to another peg, one disk at a time, and never put a bigger disk on a smaller one. The fewest moves for n disks is 2ⁿ − 1: 7 for 3 disks, 15 for 4.
Below: three ways to play the Tower of Hanoi game online, move-by-move solutions, the algorithm in code, and what the puzzle says about planning.
How to play
Pick a mode at the top and press Start. Tap a peg, then the peg to move to, or drag a disk. The game counts every move and shows how far you are from the minimum.
Planning several moves ahead.
Planning without a safety net.
Planning from a position you have never seen.
The numbers
Each extra disk doubles the moves and adds one: the minimum for n disks is 2ⁿ − 1.
| Disks | Fewest moves |
|---|---|
| 3 disks | 7 |
| 4 disks | 15 |
| 5 disks | 31 |
| 6 disks | 63 |
| 7 disks | 127 |
| 8 disks | 255 |
| 9 disks | 511 |
| 10 disks | 1,023 |
The bars grow one step per disk because the moves double. 64 disks need 18,446,744,073,709,551,615 moves.
The trick
Every solution is the same three steps. To move n disks from A to C:
Solutions
Peg A is the start, B the spare and C the goal.
For programmers
The three steps are a recursion: the solution for n disks uses the one for n − 1 disks twice. So T(n) = 2T(n − 1) + 1, which gives T(n) = 2ⁿ − 1.
function hanoi(n, from, to, spare) {
if (n === 0) return;
hanoi(n - 1, from, spare, to);
console.log('Move disk ' + n + ' from ' + from + ' to ' + to);
hanoi(n - 1, spare, to, from);
}
hanoi(3, 'A', 'C', 'B'); // 7 movesdef hanoi(n, source, target, spare):
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(3, "A", "C", "B") # 7 movespublic class Hanoi {
static void hanoi(int n, char from, char to, char spare) {
if (n == 0) return;
hanoi(n - 1, from, spare, to);
System.out.println("Move disk " + n + " from " + from + " to " + to);
hanoi(n - 1, spare, to, from);
}
public static void main(String[] args) {
hanoi(3, 'A', 'C', 'B'); // 7 moves
}
}#include <stdio.h>
void hanoi(int n, char from, char to, char spare) {
if (n == 0) return;
hanoi(n - 1, from, spare, to);
printf("Move disk %d from %c to %c\n", n, from, to);
hanoi(n - 1, spare, to, from);
}
int main(void) {
hanoi(3, 'A', 'C', 'B'); /* 7 moves */
return 0;
}Rules and formula
There are three rules and one formula: the fewest moves for n disks is 2ⁿ − 1. Each extra disk doubles the moves and adds one.
Move one disk at a time. Take only the top disk of a peg. Never place a disk on a smaller one. That is the whole puzzle.
To move n disks, move the n − 1 disks above the largest out of the way, move the largest once, then put the n − 1 disks back on top. So the count doubles and adds one: 1, 3, 7, 15, 31.
For 5 disks, 2⁵ − 1 = 31 moves. For 8 disks, the most in our game, it is 255. The legend’s 64 disks need about 18.4 quintillion moves.
Algorithm
The classic Tower of Hanoi algorithm is recursive: to move a tower, move the smaller tower above its bottom disk, move that disk, then move the smaller tower back on top. It always finds the shortest solution.
A simple loop works too. On every odd move, shift the smallest disk one peg along, always the same way round. On every even move, make the only legal move that does not touch it.
With an odd number of disks, the smallest disk heads straight for the target peg first. With an even number, it goes to the spare peg first. Get this wrong and you finish on the wrong peg.
The code section above has the recursive version in all three languages, including a short Tower of Hanoi in Java. Each one prints the same 7 moves for 3 disks.
Complexity
The time complexity of the recursive solution is O(2ⁿ), because it makes 2ⁿ − 1 moves. It needs O(n) extra memory: one level of recursion for each disk.
Moving n disks means moving n − 1 disks twice, plus one move. So T(n) = 2T(n − 1) + 1, and every extra disk doubles the work.
No. With three pegs, 2ⁿ − 1 moves is the proven minimum, so no algorithm can solve it in fewer moves. Only more pegs change that.
hanoi(n, from, to, spare): if n is 0, stop; hanoi(n − 1, from, spare, to); move disk n from “from” to “to”; hanoi(n − 1, spare, to, from).
History
The French mathematician Édouard Lucas published it in 1883 under the name N. Claus (de Siam), an anagram of Lucas d’Amiens. Its booklet told a legend of priests moving 64 golden disks in a temple at Benares.
The legend was part of the toy’s story, not ancient history. At one move a second, 64 disks would take about 585 billion years.
Psychologists use tower puzzles to study planning. The Tower of Hanoi-Revised and the Tower of London are research versions (Welsh and Huizinga, 2001; Shallice, 1982).
Five disks need 31 moves. The full move-by-move list is in the solutions above, after 3 and 4 disks.
Skills
Seeing several moves ahead: each disk waits until the smaller ones are out of the way. Psychologists use the Tower of London, a close cousin, to study planning.
Keeping track of where the smaller disks have to go while you move the larger ones.
Noticing the rhythm: the smallest disk moves every other move. Once you see it, any tower falls.
And IQ
No, but it is a classic test of planning. Psychologists use tower puzzles to study how people think ahead, and a close cousin, the Tower of London, was built for exactly that (Shallice, 1982).
Planning is an executive function, and executive function and IQ overlap without being the same. The closest IQ area is fluid reasoning: solving new problems. To see your reasoning, memory and speed in one score, take the IQ test.
The five areas of a modern IQ test
The five primary index areas of the WISC-V (children, 2014) and the WAIS-5 (adults, 2024). See WAIS-5 index scores explained.
FAQ
A puzzle with three pegs and a stack of disks in size order. Move the whole stack to another peg, one disk at a time, never putting a larger disk on a smaller one.
2ⁿ − 1 for n disks: 7 moves for 3 disks, 15 for 4, 31 for 5, 63 for 6, 127 for 7 and 255 for 8.
To move the largest disk, the n − 1 disks above it must first go to the spare peg, and afterwards they move back on top of it. So T(n) = 2T(n − 1) + 1 with T(1) = 1, which gives T(n) = 2ⁿ − 1.
Yes. Move the smallest disk every other move, always the same way round: A → C → B → A for an odd number of disks, A → B → C → A for an even number. On the moves in between, only one legal move does not use the smallest disk.
2⁶⁴ − 1 moves, about 18.4 quintillion. At one move a second that is about 585 billion years, roughly 42 times the age of the universe.
The solution for n disks is built from the solution for n − 1 disks, used twice. That is recursion, and the program is only five lines long.
The French mathematician Édouard Lucas, in 1883. He published it under the name N. Claus (de Siam), an anagram of Lucas d’Amiens, with a legend about priests moving 64 golden disks.
No. It is a planning puzzle, and practice and the smallest-disk trick make anyone faster. A full IQ test measures reasoning across many kinds of questions.
The disks start on random pegs, always stacked by size, and you gather them on the outlined peg. The game works out the minimum for that start, so a perfect run is still possible. The daily puzzle is the same for everyone.
Every move counts, and Undo never removes one. A run is Perfect when it uses the minimum number of moves with no undo and no hint.
With four pegs the puzzle needs far fewer moves. The Frame–Stewart method is the best known, and it was proved optimal for four pegs in 2014.
Move the smallest disk to the spare peg first, not the target: with an even number of disks, that is the right start. Then follow the 15-move solution listed above.
Yes. After a run, send the link: your friend plays the same tower, or the same Scramble puzzle, and sees both scores.
Yes. It is free to play, with no signup, and your scores stay in your browser.
Sources
The full picture
Each game looks at one skill. The IQ test brings speed, reasoning and memory together in one score, with your percentile and a certificate.