Let’s write programs that solve the Tower of Hanoi in Python and C. Each prints the moves for 3 disks from the left pole to the right pole. The idea is explained in The Tower of Hanoi Algorithm, so here we focus on the code and how to run it.

Solving with Recursion in Python

This is the most basic form. It turns “move the top n − 1 disks aside → move disk n → bring the n − 1 disks back” directly into a function.

def hanoi(n, src, dst, via, moves):
    if n == 0:
        return
    hanoi(n - 1, src, via, dst, moves)  # move the top n-1 disks aside
    moves.append((n, src, dst))         # move disk n
    hanoi(n - 1, via, dst, src, moves)  # bring the n-1 disks back


moves = []
hanoi(3, "left", "right", "middle", moves)
for i, (disc, src, dst) in enumerate(moves, 1):
    print(f"Move {i}: disk {disc} from {src} to {dst}")
print(f"{len(moves)} moves in total")

Save it as hanoi.py and run it with python3 hanoi.py, and it prints the following.

Move 1: disk 1 from left to right
Move 2: disk 2 from left to middle
Move 3: disk 1 from right to middle
Move 4: disk 3 from left to right
Move 5: disk 1 from middle to left
Move 6: disk 2 from middle to right
Move 7: disk 1 from left to right
7 moves in total

Change the 3 in hanoi(3, ...) and it solves any number of disks. But the number of moves is 2ⁿ − 1, so it quickly becomes enormous: about a million moves for 20 disks and about a billion for 30. Python has a limit on recursion depth (about 1,000 levels by default), but the recursion depth of the Tower of Hanoi is the number of disks plus 1, so the number of moves becomes too large long before that is a problem.

Solving Without Recursion in Python

This writes the procedure for solving by hand (the two rules in the article on how to solve it) directly as a loop. The poles are handled by the numbers 0 (left), 1 (middle) and 2 (right).

def hanoi_loop(n):
    names = ["left", "middle", "right"]
    pegs = [list(range(n, 0, -1)), [], []]  # from bottom to top
    order = [0, 2, 1] if n % 2 == 1 else [0, 1, 2]  # the order disk 1 goes around
    pos = 0  # the pole disk 1 is on (which place in order)
    moves = []
    for m in range(1, 2 ** n):
        if m % 2 == 1:
            # odd move: move disk 1 to the next pole in the chosen direction
            a = order[pos]
            pos = (pos + 1) % 3
            b = order[pos]
        else:
            # even move: of the two poles without disk 1, move the smaller onto the larger
            a, b = [p for p in range(3) if p != order[pos]]
            if not pegs[a] or (pegs[b] and pegs[b][-1] < pegs[a][-1]):
                a, b = b, a
        pegs[b].append(pegs[a].pop())
        moves.append((pegs[b][-1], names[a], names[b]))
    return moves


for i, (disc, src, dst) in enumerate(hanoi_loop(3), 1):
    print(f"Move {i}: disk {disc} from {src} to {dst}")

The output is exactly the same 7 moves as the recursive version. We have checked that, for every number of disks from 1 to 10, it gives the same moves as the recursive version.

Finding Moves Directly from Binary in Python

This calculates what to do on move m without following the moves before it. The meaning of the formulas is explained in the algorithm article.

def hanoi_bits(n):
    for m in range(1, 2 ** n):
        disc = (m & -m).bit_length()     # number of trailing 0s + 1
        src = (m & (m - 1)) % 3
        dst = ((m | (m - 1)) + 1) % 3
        yield disc, src, dst


print(list(hanoi_bits(3)))

When you run it, it prints [(1, 0, 2), (2, 0, 1), (1, 2, 1), (3, 0, 2), (1, 1, 0), (2, 1, 2), (1, 0, 2)]. Each entry is (disk, pole from, pole to), the same as the 7 moves above. This formula gives the moves from pole 0 to pole 2 for an odd number of disks, and from pole 0 to pole 1 for an even number, so if you want to move an even number of disks to the right, swap poles 1 and 2 when you use it.

Solving with Recursion in C

In C too, the form is the same as in Python.

#include <stdio.h>

static int count = 0;

void hanoi(int n, const char *src, const char *dst, const char *via) {
    if (n == 0) return;
    hanoi(n - 1, src, via, dst);
    count++;
    printf("Move %d: disk %d from %s to %s\n", count, n, src, dst);
    hanoi(n - 1, via, dst, src);
}

int main(void) {
    hanoi(3, "left", "right", "middle");
    printf("%d moves in total\n", count);
    return 0;
}

Save it as hanoi.c, compile it with cc -o hanoi hanoi.c, and run it with ./hanoi, and it prints the same 7 moves and “7 moves in total” as the Python recursive version.

Common Stumbling Blocks When Writing It

  • Mixing up the order of the arguments: In the first call, swap the “spare” pole and the “to” pole, and in the second call, swap the “from” pole and the “spare” pole. If you get this wrong, moves that break the rules come out.
  • Forgetting the stopping condition: If you do not stop at n == 0 (or n == 1), it keeps calling forever.
  • How to check: It helps to apply the moves that come out to a board, and check that no move puts a large disk on a small disk and that the number of moves is 2ⁿ − 1.