Towers of Hanoi in Python

Why this matters

Some problems are easy to state and hard to see the answer to. The Towers of Hanoi is one of them. You have three pegs and a stack of disks, and you must move the whole stack to another peg. The rules are short, but the first time you try it by hand with five disks, it takes a long time, and you may not know whether you did it in the fewest moves.

The puzzle is a good teaching example for recursion. The solution is a short function that calls itself on a smaller tower. You can prove the function is correct, count its moves with a formula, and print every move with a few lines of Python. The same pattern, solving a smaller copy of the problem first, shows up in sorting, tree walks and many other tasks.

This lesson stays with the puzzle. The idea of a base case and the call stack are covered in the first lesson of this module, and the way to turn recursion into a loop is in the explicit stack lesson.

Words used in this lesson

A disk is a flat ring with a hole in the middle. Each disk has a size, and no two disks have the same size. A peg is a rod that holds disks. There are three pegs, and this lesson calls them A, B and C.

A tower is a group of disks stacked on one peg, with the largest disk at the bottom. A move takes the top disk from one peg and places it on another peg. A move is legal only when the disk you place is smaller than the disk under it, or when the peg is empty.

A recursion is a function that calls itself on a smaller problem. A base case is the input where the function stops calling itself. The call stack is the record Python keeps of which function calls are still waiting to finish.

A spare peg is the third peg, the one that is neither the start nor the goal. In Python there is no separate character type, so a peg name such as "A" is a string of length 1.

The rules, with one disk and two disks by hand

Start with one disk on peg A. The goal is to move it to peg C. You need one move: take the disk from A and place it on C. That is the whole puzzle.

Now take two disks. The small disk sits on top of the large disk on peg A. You want both on peg C, in the same order. You cannot move the large disk first, because the small disk is on top of it. You cannot place the large disk on top of the small one, because the rule says a disk may not sit on a smaller disk.

Work it out by hand. Move the small disk from A to B. Move the large disk from A to C. Move the small disk from B to C. Three moves in total. The small disk moved out of the way first, then the large disk moved, then the small disk came back on top of it.

Notice the pattern. To move the large disk, the small one had to be on the spare peg. That is the key to the whole puzzle.

The recursive idea

Here is the idea written as a rule. Suppose you know how to move a tower of n - 1 disks from any peg to any other peg. Then you can move a tower of n disks like this:

1. Move the top n - 1 disks from the start peg to the spare peg. The goal peg is free to use as a temporary place.
2. Move the bottom disk from the start peg to the goal peg. The start peg has only that disk now, and the goal peg is empty, so the move is legal.
3. Move the n - 1 disks from the spare peg to the goal peg. Now they sit on top of the big disk, which is the right order.

Step 1 and step 3 are the same problem as the original, but with one fewer disk. That is why the function calls itself. The base case is zero disks. There is nothing to move, so the function does nothing and returns.

The function takes four inputs: the number of disks, the peg to move from, the peg to move to, and the spare peg. The function returns nothing, because its job is to print or count moves.

The order of the three steps in the code matches the order above. The recursive call for the top disks comes first, then the printed move, then the second recursive call. Changing the order breaks the puzzle, as the mistakes section shows.

Example 1: two disks, written out by the program

This program moves two disks from A to C, using B as the spare. It also moves three disks, so you can see the moves grow.

Press Run. The output is:

Two disks:
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Three disks:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

The two-disk output matches the hand solution. The first move puts disk 1 on B, which is the spare, so disk 2 can move to C.

Check that the three-disk output is legal. Disk 3, the largest, moves only once, from A to C. Just before that move, disks 1 and 2 are both on peg B, in the right order, and peg C is empty. So disk 3 can go onto C with nothing under it to break the rule.

Keep a picture of the three pegs while you read the lines. Each move takes the top disk of one peg and puts it on a peg where it lands on a larger disk or on nothing. The program never checks this. The order of the recursive calls guarantees it.

Example 2: counting the moves

Printing every move gets long fast. A tower of ten disks needs over a thousand lines. Often you only need the number of moves. The program can count them instead.

The function below does the same recursive steps, but instead of printing each move it adds one to a counter. The counter is a global variable called moves. Every call adds to the same number.

The output is:

n=0 moves=0 2^n-1=0
n=1 moves=1 2^n-1=1
n=2 moves=3 2^n-1=3
n=3 moves=7 2^n-1=7
n=4 moves=15 2^n-1=15
n=5 moves=31 2^n-1=31
n=6 moves=63 2^n-1=63
n=7 moves=127 2^n-1=127
n=8 moves=255 2^n-1=255
n=9 moves=511 2^n-1=511
n=10 moves=1023 2^n-1=1023
n=64 formula: 18446744073709551615
2**63 - 1 = 9223372036854775807
20 disks: 1048575

The counted moves match 2 ** n - 1 for every n from 0 to 10. The ** operator raises a number to a power, so 2 ** 3 is 8.

Why does the formula hold? Count the moves for the recursive function. Let M(n) be the number of moves for n disks. Step 1 takes M(n - 1) moves, step 2 takes one move, and step 3 takes M(n - 1) moves. So M(n) = 2 times M(n - 1) + 1. With zero disks, there are zero moves. Then M(1) = 1, M(2) = 3, M(3) = 7, and so on. Each value is one more than twice the value before, and that pattern gives 2^n - 1.

Check the claim with a case you can count: the table shows that three disks need seven moves, and the printed three-disk solution above has seven lines. The formula can be used to plan. For 20 disks, the answer is 2^20 - 1, which is 1048575 moves.

The line for 64 disks shows the size of the answer. A Python int has no fixed size, so the exact count, 18446744073709551615, is printed in full. That number is larger than the largest signed 64-bit whole number, which is 9223372036854775807 as the line for 2**63 - 1 shows. A move per second for that many moves would take about 585 billion years, counting a year as 365.25 days. You can plan with the formula, but you cannot run the count for 64 disks. The function would need about 2 to the power 65 calls.

Example 3: following the pegs

Printing only the moves makes it hard to check the rules. A better way is to keep each peg as a list of disks and print all three pegs after every move. This program does that for three disks. The first item in each list is the top disk.

The program uses collections.deque, which is a list that is fast to add to and remove from at either end. The methods appendleft and popleft work at the top of each peg. The program turns each deque into a plain list before printing it, so the output reads like the other lists in this lesson. The function move takes a disk from the top of one peg and checks the target before it places the disk. If the target's top disk is smaller, the function raises a ValueError and the program stops. That check is the rule from the start of the lesson, written in code.

The output is:

  A: [1, 2, 3]  B: []  C: []
Move disk 1 from A to C
  A: [2, 3]  B: []  C: [1]
Move disk 2 from A to B
  A: [3]  B: [2]  C: [1]
Move disk 1 from C to B
  A: [3]  B: [1, 2]  C: []
Move disk 3 from A to C
  A: []  B: [1, 2]  C: [3]
Move disk 1 from B to A
  A: [1]  B: [2]  C: [3]
Move disk 2 from B to C
  A: [1]  B: []  C: [2, 3]
Move disk 1 from A to C
  A: []  B: []  C: [1, 2, 3]

Read the states in order and you can see the whole solution. The smallest disk moves at steps 1, 3, 5 and 7, which is every other move, because each of the other moves moves a larger disk. Disk 3 moves once, at step 4, when peg B holds disks 1 and 2 and peg C is empty. The final line shows all three disks on peg C in their original order, from largest at the bottom to smallest at the top.

No error appears, so every move passed the check. If a move were illegal, for example placing disk 2 on top of disk 1, the program would stop with the message Disk 2 cannot go on disk 1. That is a useful habit for any move puzzle. You do not need to trust the recursion. You can test each step against the rules.

Example 4: why the order of the three steps matters

The fourth example is a harder check. It shows what goes wrong when the recursive calls are written in the wrong order. Read the code, then the output, and work out why the output is not a valid solution.

The output is:

Move disk 1 from A to C
Move disk 2 from A to C
Move disk 1 from B to C

The first call moves the top disk to C, not to the spare peg. Then the program moves disk 2 from A to C, placing the large disk on top of the small disk. That breaks the rule. The function swapped the roles of the goal peg and the spare peg in the first recursive call. Disk 1 has to go to B in that step, not to C.

The program does not check the rules. It prints whatever order the calls produce, so you have to check the output yourself. A quick test is to keep a list of which disks sit on each peg and reject any move that puts a larger disk on a smaller one, as Example 3 does.

Common mistakes

Swapping the spare and goal pegs. In the first recursive call, the goal of the sub-problem is the spare peg, and the spare for the sub-problem is the goal peg. Writing solve(n - 1, source, target, spare) instead of solve(n - 1, source, spare, target) produces the output in Example 4. Read the call and ask: where does the top group of disks go first? The answer is the spare peg.

Forgetting the base case. If the function has no if n == 0 check, it calls itself with n - 1, which keeps going below zero. The chain of waiting calls grows until Python stops it. The output is a traceback that ends with this line:

RecursionError: maximum recursion depth exceeded

The traceback shows the same call line over and over, which is the sign of a missing or unreachable base case. The function solve from Example 1 with its base case removed gives this error after a long list of repeated lines.

Counting moves by printing, then counting the lines. This works for small towers, but it is slow for large ones. Use a counter, as in Example 2, when you only need the total. Use the formula 2 ** n - 1 when you need the total before you run anything.

Printing a move that puts a bigger disk on a smaller one. The recursion avoids this when the order is right. If you change the code, run the program from Example 3 with two or three disks, and the peg check will stop it at the first illegal move.

Practice

Exercise 1

Write the moves for two disks when the start is A and the goal is B, with C as the spare. Give the three moves in order.

Show the answer

Move disk 1 from A to C. Move disk 2 from A to B. Move disk 1 from C to B. The spare here is C, so the small disk goes there first.

Exercise 2

How many moves does a tower of five disks need?

Show the answer

Use 2 ** 5 - 1, which is 32 - 1, so 31 moves. The table in Example 2 also shows 31 for n = 5.

Exercise 3

Change the program in Example 2 so it prints only the count for 20 disks, on one line. What number does it print?

Show the answer

Replace the loop with a call to count_moves(20) and print moves. It prints 1048575, which is 2 ** 20 - 1. The function makes about two million calls for 20 disks, which is fine. For 30 disks it would make about two billion calls, so use the formula there.

Exercise 4

Explain in your own words why the first recursive call must send the top stack to the spare peg, not to the goal peg. Use the two-disk case in your answer.

Show the answer

With two disks, the goal peg C must be empty when the large disk moves. If disk 1 goes to C first, disk 2 cannot go to C later without covering disk 1 with a larger disk, so the first move has to be to the spare peg B. Then disk 2 moves to C, and disk 1 comes back on top of it.

Exercise 5

What does solve(0, "A", "C", "B") print?

Show the answer

It prints nothing. The base case returns at once, and zero disks need zero moves.

Summary

• The puzzle is solved by moving the top n - 1 disks to the spare peg, moving the bottom disk to the goal, and then moving the n - 1 disks onto it.
• The recursive function has a base case at zero disks, and its two recursive calls each solve a smaller tower.
• A tower of n disks needs 2 ** n - 1 moves, which follows from M(n) = 2 times M(n - 1) + 1.
• Python integers have no fixed size, so the count is exact for any number of disks. The limit is the time it takes to run the calls.
• The order of the three steps matters. Swapping the spare and goal pegs in the first call gives an illegal move sequence.