Tower Of Hanoi

Problem

Move n disks from a source peg to a target peg using an auxiliary peg. Only one disk may be moved at a time, and a larger disk may never be placed on top of a smaller one.

Approach

Classic recursion: move n-1 disks from source to auxiliary, move the largest disk from source to target, then move n-1 disks from auxiliary to target. Base case: n == 0 (do nothing).

When to Use

Pure recursive decomposition — the canonical example. Demonstrates how recursion breaks problems into identical sub-problems. Also: understanding call stack depth and O(2^n) explosion.

Complexity

Time	O(2^n) — number of moves
Space	O(n) — recursion depth

Implementation

SolutionTestsChallenge

tower_of_hanoi

Tower of Hanoi — move n disks between pegs.

Problem

Move n disks from a source peg to a target peg using an auxiliary peg. Only one disk may be moved at a time, and a larger disk may never be placed on top of a smaller one.

Approach

Classic recursion: move n-1 disks from source to auxiliary, move the largest disk from source to target, then move n-1 disks from auxiliary to target. Base case: n == 0 (do nothing).

When to use

Pure recursive decomposition — the canonical example. Demonstrates how recursion breaks problems into identical sub-problems. Also: understanding call stack depth and O(2^n) explosion.

Complexity

Time: O(2^n) — number of moves Space: O(n) — recursion depth

tower_of_hanoi

tower_of_hanoi(
    n: int,
    source: str = "A",
    target: str = "C",
    auxiliary: str = "B",
) -> list[tuple[str, str]]

Solve Tower of Hanoi for n disks, returning moves as (from, to) tuples.

tower_of_hanoi(1) [('A', 'C')] tower_of_hanoi(2) [('A', 'B'), ('A', 'C'), ('B', 'C')]

Source code in src/algo/recursion/tower_of_hanoi.py

def tower_of_hanoi(
    n: int,
    source: str = "A",
    target: str = "C",
    auxiliary: str = "B",
) -> list[tuple[str, str]]:
    """Solve Tower of Hanoi for *n* disks, returning moves as (from, to) tuples.

    >>> tower_of_hanoi(1)
    [('A', 'C')]
    >>> tower_of_hanoi(2)
    [('A', 'B'), ('A', 'C'), ('B', 'C')]
    """
    moves: list[tuple[str, str]] = []

    def solve(disks: int, src: str, tgt: str, aux: str) -> None:
        if disks == 0:
            return
        solve(disks - 1, src, aux, tgt)
        moves.append((src, tgt))
        solve(disks - 1, aux, tgt, src)

    solve(n, source, target, auxiliary)
    return moves

tests/recursion/test_tower_of_hanoi.py

"""Tests for the Tower of Hanoi problem."""

from hypothesis import given
from hypothesis import strategies as st

from algo.recursion.tower_of_hanoi import tower_of_hanoi


class TestTowerOfHanoi:
    def test_one_disk(self) -> None:
        assert tower_of_hanoi(1) == [("A", "C")]

    def test_two_disks(self) -> None:
        assert tower_of_hanoi(2) == [("A", "B"), ("A", "C"), ("B", "C")]

    def test_three_disks(self) -> None:
        moves = tower_of_hanoi(3)
        assert len(moves) == 7
        assert moves[0] == ("A", "C")
        assert moves[-1] == ("A", "C")

    def test_zero_disks(self) -> None:
        assert tower_of_hanoi(0) == []

    def test_custom_peg_names(self) -> None:
        moves = tower_of_hanoi(1, source="X", target="Z", auxiliary="Y")
        assert moves == [("X", "Z")]

    @given(n=st.integers(min_value=1, max_value=10))
    def test_move_count_is_2n_minus_1(self, n: int) -> None:
        assert len(tower_of_hanoi(n)) == 2**n - 1

    @given(n=st.integers(min_value=1, max_value=8))
    def test_moves_are_valid(self, n: int) -> None:
        """Simulate moves and verify no larger disk is placed on a smaller one."""
        moves = tower_of_hanoi(n)
        pegs: dict[str, list[int]] = {
            "A": list(range(n, 0, -1)),
            "B": [],
            "C": [],
        }
        for src, tgt in moves:
            disk = pegs[src].pop()
            if pegs[tgt] and pegs[tgt][-1] < disk:
                msg = f"Invalid move: disk {disk} onto disk {pegs[tgt][-1]}"
                raise AssertionError(msg)
            pegs[tgt].append(disk)
        # All disks should be on target peg
        assert pegs["A"] == []
        assert pegs["B"] == []
        assert pegs["C"] == list(range(n, 0, -1))

Implement it yourself

Run: just challenge recursion tower_of_hanoi

Then implement the functions to make all tests pass. Use just study recursion for watch mode.

Reveal Solution

tower_of_hanoi

Tower of Hanoi — move n disks between pegs.

Problem

Move n disks from a source peg to a target peg using an auxiliary peg. Only one disk may be moved at a time, and a larger disk may never be placed on top of a smaller one.

Approach

Classic recursion: move n-1 disks from source to auxiliary, move the largest disk from source to target, then move n-1 disks from auxiliary to target. Base case: n == 0 (do nothing).

When to use

Pure recursive decomposition — the canonical example. Demonstrates how recursion breaks problems into identical sub-problems. Also: understanding call stack depth and O(2^n) explosion.

Complexity

Time: O(2^n) — number of moves Space: O(n) — recursion depth

tower_of_hanoi

tower_of_hanoi(
    n: int,
    source: str = "A",
    target: str = "C",
    auxiliary: str = "B",
) -> list[tuple[str, str]]

Solve Tower of Hanoi for n disks, returning moves as (from, to) tuples.

tower_of_hanoi(1) [('A', 'C')] tower_of_hanoi(2) [('A', 'B'), ('A', 'C'), ('B', 'C')]

Source code in src/algo/recursion/tower_of_hanoi.py

def tower_of_hanoi(
    n: int,
    source: str = "A",
    target: str = "C",
    auxiliary: str = "B",
) -> list[tuple[str, str]]:
    """Solve Tower of Hanoi for *n* disks, returning moves as (from, to) tuples.

    >>> tower_of_hanoi(1)
    [('A', 'C')]
    >>> tower_of_hanoi(2)
    [('A', 'B'), ('A', 'C'), ('B', 'C')]
    """
    moves: list[tuple[str, str]] = []

    def solve(disks: int, src: str, tgt: str, aux: str) -> None:
        if disks == 0:
            return
        solve(disks - 1, src, aux, tgt)
        moves.append((src, tgt))
        solve(disks - 1, aux, tgt, src)

    solve(n, source, target, auxiliary)
    return moves