To solve the Tower of Hanoi, there are only two steps to remember. If you repeat them in turn, you can move the tower in the fewest moves, however many disks there are. This article explains the case of moving the tower from the left pole to the right pole (for the rules, see What Is the Tower of Hanoi?). The disks are numbered 1, 2, 3… from smallest to largest.

The Solution Is Two Steps Repeated

  1. Odd-numbered moves (move 1, 3, 5…): Move the smallest disk (1) to the next pole in a fixed direction.
  2. Even-numbered moves (move 2, 4, 6…): Make the move available for the disks other than 1. There is always only one such move.

That is all. Disk 1 moves every other move, and in between, a disk other than 1 moves once.

How to Choose the Direction for the Small Disk

The direction for disk 1 depends on the number of disks. Think of the three poles as connected in a circle, and when it reaches the end, it wraps around to the other end. When you move the left tower to the right, the order is:

Number of disksOrder for moving disk 1
Odd (3, 5, 7…)left → right → middle → left…
Even (4, 6, 8…)left → middle → right → left…

The way to remember it is “with an odd number of disks, on the first move put disk 1 straight onto the pole you want to move to.” With an even number, on the first move put it on the other pole (the middle). Once you decide the direction, never change it until the end.

If you want to move to the middle pole, swap “right” and “middle” in the table.

Check with 3 Disks

With 3 disks (odd), disk 1 goes around in the order “left → right → middle → left”. The gold disk is the one moved on that move.

  1. 321 Start
  2. 321 Move 1 1 to the right
  3. 321 Move 2 2 to the middle
  4. 321 Move 3 1 to the middle
  5. 213 Move 4 3 to the right
  6. 123 Move 5 1 to the left
  7. 132 Move 6 2 to the right
  8. 321 Move 7 1 to the right

You can see that on moves 1, 3, 5 and 7, disk 1 is just going around, and moves 2, 4 and 6 are “the only move available that does not involve 1.”

Why the Even-Numbered Move Is Decided

On an even-numbered move, you compare the top disks of the two poles that do not have disk 1. You have no choice but to move the smaller one onto the larger one (or onto an empty pole).

  • Nothing can be placed on disk 1 (because there is no disk smaller than 1).
  • Of the other two poles, you cannot put a large disk on a small disk.

So there is always only one move available. The only place you can be unsure is the direction of 1 on odd-numbered moves, and once you decide it at the start, the moves go forward without any thinking.

The Idea of “Move the Top Aside, Carry the Large One”

Apart from memorizing the steps, there is a way to think about why this works. To move a tower of n disks from the left to the right, you can split it into three parts:

  1. Move the top n − 1 disks aside to the middle.
  2. Carry the largest disk to the right.
  3. Move the n − 1 disks in the middle to the right.

Parts 1 and 3 are the problem “move a tower with one fewer disk”, so you can use the same idea again. With 4 disks it is “move 3 aside → carry 4 → bring the 3 back”, and to move 3 aside it is “move 2 aside → carry 3 → bring the 2 back”… and so on, splitting into smaller problems. This idea also shows why the number of moves is 2ⁿ − 1 (the minimum-moves formula).

How to Get Back on Track When You Are Lost

Even if you forget the steps and end up with a scrambled arrangement, it is fine. With this way of thinking, you can get back on track from anywhere.

  1. Among the disks not yet stacked correctly on the right pole, find the largest one. This is the disk to carry next.
  2. To carry that disk to the right, you need to gather all the smaller disks on the one remaining pole, which is neither where it is now nor the right pole.
  3. Gathering the small disks is the same idea repeated. Think of the pole you are gathering them on as the “target pole”, and start again from 1.

The tip is to decide the destinations from the large disks in order. The app’s Puzzles mode (the way of playing where you match scattered disks to a target shape) can also be solved with this idea.

Tips for Solving

  • Count the moves: On odd-numbered moves you always move disk 1, so if you know which move number you are on, you will not be unsure which disk to move next.
  • Larger disks move less: Disk 1 moves in half of all moves, but the largest disk moves only once. If you are moving a large disk many times, you are taking a detour.
  • Start with 3 or 4 disks: Until the two steps become second nature, it is a good idea to repeat them several times with fewer disks. When you are used to it, increase to 5 and 7.

Steps for Each Number of Disks

The steps for each number of disks and checkpoint positions are collected in these articles.

Play to Try It

Try the two steps on the board below. Tap a pole to lift its top disk, and tap another pole to put it there. You start with 4 disks (even), so on the first move, move 1 to the middle.

4321
Moves: 0 (fewest 15)

Move the whole tower from the left pole to the right pole. Tap a pole to pick up its top disk.