Tower of Hanoi: Frequently Asked Questions

There is one, and it is mechanical rather than clever: on every odd-numbered move, move the smallest disk one tower in the same direction — left for an odd number of disks, right for an even number, wrapping round at the ends, so with three disks its very first move wraps from A round to C. On every even-numbered move there is only ever one legal move that does not touch the smallest disk, so you make it without thinking. Alternate the two and you play a perfect game without planning a single step ahead. The strategies page works through it.

Start with the whole stack on the left tower, smallest disk on top. The goal is the same stack on the right tower. Three rules: move one disk at a time, only ever the top disk of a tower, and never place a larger disk on a smaller one. With three disks the shortest game is seven moves in three groups: A→C, A→B, C→B builds the two smallest disks on the middle tower; A→C lets the largest disk cross; and B→A, B→C, A→C rebuilds those two on top of it. How to play, with a practice board.

Easy to learn, and difficult in exactly one way: it gets twice as long with every disk you add. Three disks take seven moves, and most people — children from about six — finish on their first attempt. Somewhere around five or six disks trial and error stops working and you need a method, and the hard part of the method is trusting moves that look backwards, such as piling a whole stack on the middle tower when the goal is on the right. Once the recursive idea clicks, every size is the same puzzle. Why the recursive idea is the whole puzzle.

There is no governing body that ratifies Tower of Hanoi speed records the way there is for the Rubik's cube, so claimed times are not comparable and usually do not say how many disks were used — which is the only number that matters. Work it out instead: a perfect game of n disks is 2ⁿ − 1 moves, and a practised player sustains roughly two moves a second. That is about four seconds for three disks, around nine minutes for ten disks and its 1,023 moves, and about four and a half hours for 15 disks and its 32,767. The board on this site keeps your fewest moves for each disk count in your browser, and shows your time on the result screen. The calculator gives the time for any size.

2ⁿ − 1, and that is a proven floor rather than a best-known result. Three disks need 7 moves, four need 15, five need 31, ten need 1,023, and 15 need 32,767. The proof has two halves: the recursive method achieves that number, and no solution can beat it, because the largest disk must move at least once and every smaller disk above it must be cleared onto the spare tower first and brought back afterwards. Both halves of the proof, in full.

T(n) = 2·T(n − 1) + 1, with T(0) = 0. It reads straight off the method: to move n disks you move n − 1 disks out of the way, move one disk across, then move those n − 1 disks back — two smaller solutions plus a single move. Unrolling it gives T(n) = 2ⁿ − 1, which you can check by induction: if T(n − 1) = 2ⁿ⁻¹ − 1 then T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1. Solving the recurrence, step by step.

Not in the computational sense, despite the exponential number of moves. The algorithm is a few lines long, deciding the next move takes constant time, and the solution is only exponentially long because the answer itself is — printing 2ⁿ − 1 moves cannot be done in fewer than 2ⁿ − 1 steps. It is not NP-hard, and finding the shortest route between two arbitrary legal positions on three pegs is also solvable efficiently. The genuinely hard version is the four-peg puzzle, whose optimal solution was conjectured in 1941 and not proved until Thierry Bousch settled it in 2014. The algorithm and what it costs.

Use the Frame–Stewart method. With four rods you no longer move n − 1 disks in one lump: you choose a split k, move the top k disks to a spare rod using all four rods, move the remaining n − k disks to the target using only three rods — the spare is occupied, so that part is the classic puzzle — then move the k disks on top. Trying every k and taking the best gives the optimal count, which collapses spectacularly: 15 disks drop from 32,767 moves on three rods to 129 on four. Play the four-peg puzzle.

Divide and conquer, expressed as recursion. The standard solution is one function — move n − 1 disks from the source to the spare, move disk n from the source to the target, move those n − 1 disks from the spare to the target — with the base case doing nothing when n reaches zero. There is an equivalent iterative algorithm that uses no recursion at all: repeatedly move the smallest disk one tower in a fixed direction, then make the only other legal move. Both produce exactly the same sequence of moves, because the optimal solution is unique. The algorithm, line by line.

One recursive function and three parameters: void hanoi(int n, char from, char to, char via) — if n is zero, return; otherwise call hanoi(n − 1, from, via, to), print the move from → to, then call hanoi(n − 1, via, to, from). Call it as hanoi(3, 'A', 'C', 'B'). Collect the moves into a std::vector<std::pair<char, char>> instead of printing if the caller needs them, and keep n a plain int: with an unsigned parameter, a negative count passed in by mistake silently becomes about four billion, and the recursion runs until the stack overflows instead of failing a simple n < 0 check. The full C++ program, explained line by line.

Two different uses of a stack, and it is worth keeping them apart. The pegs are stacks: each tower is last-in-first-out, you only ever touch the top disk, and a move is a pop from one tower and a push onto another — which is why the rule check is a single comparison against the top of the destination. Separately, an explicit stack can replace recursion: push the whole job (n, from, to, via), then loop — pop a job, and if it has disks, push its three parts in reverse order: the second transfer, the single move of disk n, then the first transfer. The reverse order matters because a stack hands back the last thing pushed first. That is what the language runtime is doing for you in the recursive version. The solution with no recursion at all.

In AI the puzzle is a search problem, not a formula. Each state is an assignment of every disk to a peg, so there are 3ⁿ of them, and the legal moves are the edges between them; a search — breadth-first, A* or iterative-deepening A* with a heuristic such as the number of disks not yet on the target peg — finds the shortest path from the start state to the goal. It has been a standard test problem since the General Problem Solver of Newell, Shaw and Simon, because it is a clean example of means–ends analysis and of goal decomposition: the sub-goal 'move the largest disk' can only be reached by first satisfying a sub-goal that appears to undo progress. Note that the recursive algorithm is not search — it is the known solution, and it never explores a state it does not use. The same puzzle as a psychology task.