The Iterative Tower of Hanoi Solution

The recursive algorithm is the natural way to solve the Tower of Hanoi, and for a person it is a poor one: it asks you to keep a stack of unfinished jobs in your head. The iterative solution asks for nothing. You look at the board, apply one of two rules, and move. It needs no memory beyond the move number, and it plays the optimal game.

The two rules

Number the moves from 1.

1. On odd-numbered moves, move the smallest disk one step round its circuit. For an odd number of disks the circuit is A → C → B → A. For an even number it runs the other way, A → B → C → A. The smallest disk never reverses and never misses its turn.
2. On even-numbered moves, make the only legal move that does not involve the smallest disk.

1. An odd number of disksA → C → B → A

   With three, five or any odd number of disks, disk 1 goes A, then C, then B, then back to A, and round again for the whole game. The largest disk has to end on C, and this is the direction that puts it there.

2. An even number of disksA → B → C → A

   Add one disk and the ring reverses: disk 1 now goes A, then B, then C, then back to A. Nothing else about the algorithm changes — the second rule never mentions a direction, because it never has a choice.

Rule 2 always has exactly one move to offer. The smallest disk is on one tower; look at the other two. Whatever is on top of them is bigger than disk 1. If one of them is empty, the only legal move is the other’s top disk onto it. If neither is, the smaller of their two top disks can move onto the larger, and not the other way round. Either way there is one choice, and it is forced.

That is the whole algorithm. The board below plays it, and says after each move which rule chose it.

3 disks4 disks5 disks

4

3

2

1

A

B

C

4 disks on tower A. 15 moves to go.Step 0 of 15

Step through the moves. Anywhere in this player, the left and right arrow keys step, space plays and pauses, and Home and End jump to the start and the end.

With 4 disks, disk 1 circles A → B → C → A. Move 1 is odd, so it belongs to disk 1: one step round, to tower B.

Why it works

The two rules are not a different solution that happens to be as short. They are the recursive solution, described from the outside, and three facts show it.

The smallest disk moves on every odd move. In the recursive solution, disk 1’s moves are exactly the odd-numbered ones: disk k first moves on move 2ᵏ⁻¹ and then every 2ᵏ moves, which for disk 1 means moves 1, 3, 5 and so on. (The binary page shows why.) So every even move belongs to some other disk.

The smallest disk always circles the same way. Take a transfer of n disks from a source S to a target T, with spare X. The claim is that disk 1 circles S → T → X → S when n is odd, and S → X → T → S when n is even. For one disk it moves S → T, which fits. For n disks, the transfer is an (n − 1)-disk transfer from S to X followed by one from X to T. If n is odd, n − 1 is even, so by the claim disk 1 circles S → T → X in the first half and X → S → T in the second — and those are the same circuit. If n is even, the halves give S → X → T and X → T → S, again one circuit. So the direction never changes, at any size.

The other moves are forced. On an even move the recursive solution moves some disk other than disk 1, legally. Rule 2 says there is only one such move available. So it is the move the recursive solution makes.

Put together: on odd moves the rules make the recursive solution’s move, and on even moves they make the only move it could possibly make. The two sequences are identical — which they had to be, because the shortest solution is unique.

The three-pair version

There is an even more mechanical way to state the same algorithm, and it is the one most often seen in code. Cycle through three pairs of towers, and on each move make the one legal move between that pair, in whichever direction it goes:

It is the two rules seen from further away. The odd-numbered moves visit the pairs in the order that walks round the smallest disk’s circuit, and disk 1 is always on one of the two towers in the pair, so the legal move between them is always disk 1’s. On the even-numbered moves, the pair is always the two towers disk 1 is not on. The method never needs to know which disk is the smallest — the pairs do that work.

In code

Each language page on this site uses a different non-recursive method, and every listing is run against the recursive solution for three, four and five disks:

• Python uses the two rules, with the towers as lists.
• C++ uses the three pairs of towers.
• C keeps no towers at all, and reads each move from the binary digits of its number.
• Java replaces the recursion with an explicit stack of jobs, which works for any recursive function, not only this one.

Recursive or iterative?

Neither is faster in any way that matters; both have to make 2ⁿ − 1 moves. The recursive version is the one to read, because its correctness is obvious from its shape. The iterative version is the one to play, because a person can follow it without holding anything in their head — which is why it is the shortcut in Tower of Hanoi strategies. And only the recursive idea extends to a board that is already part-way through: if the largest disk is already where it belongs, skip it and solve the rest. That is how the solver finds the shortest finish from any position.

Frequently asked questions

How do you solve Tower of Hanoi iteratively?

Repeat two rules until every disk is on the goal tower. On odd-numbered moves, move the smallest disk one step round a fixed circuit: A to C to B and back to A for an odd number of disks, A to B to C and back to A for an even number. On even-numbered moves, make the only legal move that does not involve the smallest disk.

Why does the smallest disk always move in the same direction?

Because the recursion never reverses it. A transfer of n disks is a transfer of n − 1 disks onto the spare followed by one onto the target, and the smallest disk's direction in those two halves turns out to be the same cycle. By induction it holds at every size, and its direction depends only on whether the number of disks is odd or even.

Is the iterative solution the same as the recursive one?

Yes, move for move. The shortest Tower of Hanoi solution is unique, and both methods produce it, so the two lists are identical — only the way of finding each move differs.

Can the iterative method solve a partly solved puzzle?

Not in general. The two rules describe the shortest solution from a full stack; started from an arbitrary position they may still finish, but not necessarily in the fewest moves. For the shortest solution from any position, use the recursive method generalised to handle disks that are already in place, which is what the solver on this site does.

Keep reading

• The History of the Tower of HanoiÉdouard Lucas, the 1883 puzzle sold under a false name, the legend of the sixty-four golden disks, and what the puzzle went on to become.
• Why the Minimum Is 2ⁿ − 1 MovesThe full proof that 2ⁿ − 1 moves is both achievable and unbeatable, why the shortest solution is unique, and how the moves divide between the disks.
• Tower of Hanoi, Binary and Gray CodeWhich disk moves on any move, read straight off the binary digits of the move number — and the Gray code that changes exactly the same bit.
• Recursion, Explained with the Tower of HanoiBase cases, the leap of faith and the call stack, taught on the one puzzle that recursion makes easy.
• The Tower of Hanoi algorithmThe recursive solution running line by line, its proof, and its complexity — in pseudocode and six languages.