Tower of Hanoi in Python

Run it yourself

Save the listing as hanoi.py and run it:

python hanoi.py

It prints the seven moves of the three-disk puzzle:

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

Change the 3 in the call to solve a bigger puzzle. Every disk you add doubles the output, plus one line.

Line by line

Not what each line says — the listing says that — but why it has to be there:

Why those three lines are enough — the correctness proof, the recurrence and the complexity — is on the Tower of Hanoi algorithm page, and holds for every language here.

Python’s recursion limit

Python refuses to recurse past a fixed depth — 1,000 frames by default in CPython, which sys.getrecursionlimit() reports — and raises RecursionError instead. For plenty of recursive functions that is a real constraint. For this one it never is.

The recursion only ever goes n + 1 calls deep, because each call finishes before its sibling starts: count the rows in the call stack above, and three disks never need more than four. So the limit would come into play at around a thousand disks, and a thousand-disk puzzle takes 2¹⁰⁰⁰ − 1 moves — a number with 302 digits. The program would never get far enough through its output to reach the stack’s edge.

Counting the moves

def minimum_moves(n):
    """2**n - 1, exactly. Python integers grow as large as they need to."""
    return 2**n - 1


for n in (3, 10, 64):
    print(f"{n} disks: {minimum_moves(n)} moves")

python count_moves.py

3 disks: 7 moves
10 disks: 1023 moves
64 disks: 18446744073709551615 moves

Python integers have no fixed width. 2**64 - 1 is exactly 18,446,744,073,709,551,615 with no special type, no import and no overflow, and 2**1000 - 1 would be exact too. That is unusual among the languages here: in Java the obvious expressions quietly give 0, and in JavaScript they quietly round.

Without recursion

def hanoi_iterative(n):
    pegs = {"A": list(range(n, 0, -1)), "B": [], "C": []}
    # Disk 1 always travels the same way round: A, C, B for an odd n, A, B, C for an even n.
    cycle = "ACB" if n % 2 == 1 else "ABC"

    for move in range(1, 2**n):
        smallest_at = cycle[(move // 2) % 3]
        if move % 2 == 1:
            # Odd moves: disk 1 steps on to the next tower in its cycle.
            source, target = smallest_at, cycle[(move // 2 + 1) % 3]
        else:
            # Even moves: the one legal move that leaves disk 1 alone.
            a, b = (peg for peg in "ABC" if peg != smallest_at)
            if not pegs[a] or (pegs[b] and pegs[b][-1] < pegs[a][-1]):
                source, target = b, a
            else:
                source, target = a, b
        disk = pegs[source].pop()
        pegs[target].append(disk)
        print(f"Move disk {disk} from {source} to {target}")


if __name__ == "__main__":
    hanoi_iterative(3)

python hanoi_iterative.py

This version keeps the towers as three lists, largest disk first, and makes one pass of the loop per move. Two rules choose every move.

On odd-numbered moves, the smallest disk steps on to the next tower of its circuit: "ACB" for an odd number of disks, "ABC" for an even number. Disk 1 has made move // 2 moves before this one, so cycle[(move // 2) % 3] is always the tower it is standing on, and the next letter along is where it goes.

On even-numbered moves, the two towers that do not hold disk 1 allow exactly one legal move between them — a smaller top disk onto a larger one, or onto an empty tower — and the if works out which way round it goes by comparing their top disks.

It prints the same seven lines as the recursive program, and at every size the same moves in the same order. The iterative solution explains why two such plain rules reproduce the recursion exactly.

Keeping the moves instead of printing them

To work with the moves rather than print them, give the function a list as a fifth argument, replace the print with moves.append((n, source, target)), and pass the list along in both recursive calls. Nothing else changes.

Bear in mind what you are collecting. The list holds 2ⁿ − 1 tuples: about a million at twenty disks — roughly 75 MB in CPython — and a billion at thirty, roughly 75 GB, more memory than most machines have. If you only need the moves one at a time, yield them instead of storing them, as the JavaScript generator does.

The same algorithm in other languages

• Tower of Hanoi in JavaScriptWhy 2 ** 64 − 1 prints the wrong number, BigInt, and a generator that hands out one move at a time.
• Tower of Hanoi in JavaWhy (1L << 64) − 1 is zero, counting with BigInteger, and the same solution driven by an explicit stack.
• Tower of Hanoi in CUndefined shifts, uint64_t, and a loop that reads every move straight off the bits of the move number.
• Tower of Hanoi in C++Collecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.
• Tower of Hanoi in C#Top-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

Frequently asked questions