Tower of Hanoi in C++

Run it yourself

Save the listing as hanoi.cpp and run it:

g++ -std=c++17 hanoi.cpp -o hanoi
./hanoi

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.

Returning moves, not printing them

The recursive listing on every other page of this cluster prints each move the moment it is made. This one records them, and that small change is the idiomatic one in C++: the solver no longer decides what happens to its answer. main prints the list, but a test could compare it against an expected vector, and a GUI could animate it at its own pace.

The cost is memory the printing version never uses. The vector ends up holding all 2ⁿ − 1 moves, and a Move is 8 bytes on a typical platform — so twenty disks is about 8 MB, and thirty disks is about 8.6 GB. If you know the size up front, moves.reserve((1ULL << n) - 1) saves the vector from reallocating as it grows.

Counting the moves at compile time

#include <cstdint>
#include <iostream>
#include <limits>

// The recurrence itself: T(0) = 0 and T(n) = 2T(n - 1) + 1. constexpr lets
// the compiler run it, and no step on the way to 64 disks overflows.
constexpr std::uint64_t minimum_moves(int n) {
    return n == 0 ? 0 : 2 * minimum_moves(n - 1) + 1;
}

// Checked while compiling: if either were false, this file would not build.
static_assert(minimum_moves(3) == 7);
static_assert(minimum_moves(64) == std::numeric_limits<std::uint64_t>::max());

int main() {
    constexpr std::uint64_t moves = minimum_moves(64);
    std::cout << "64 disks: " << moves << " moves\n";

    // Unsigned arithmetic wraps rather than overflowing: one move more is zero.
    std::cout << "one more: " << moves + 1 << '\n';
}

g++ -std=c++17 count_moves.cpp -o count_moves
./count_moves

64 disks: 18446744073709551615 moves
one more: 0

constexpr lets the compiler run a function while it builds the program, and static_assert stops the build if what it finds is false. So this listing does more than print 2⁶⁴ − 1: it cannot be compiled at all unless minimum_moves(64) equals std::numeric_limits<std::uint64_t>::max(), the largest value an unsigned 64-bit integer holds. The function is the recurrence from the algorithm page, T(n) = 2T(n − 1) + 1, run by the compiler — and it never overflows on the way up, because 2 × (2⁶³ − 1) + 1 is exactly 2⁶⁴ − 1.

A constant expression also changes what a mistake costs. In C, (UINT64_C(1) << 64) - 1 is undefined behaviour that compiles and runs. Here, constexpr std::uint64_t moves = (std::uint64_t{1} << 64) - 1; does not compile: a compiler evaluating a constant is required to reject undefined behaviour it meets, and GCC reports that the shift is greater than or equal to the precision of its left operand. Drop the constexpr and the line is an ordinary run-time calculation again — exactly as undefined as it is in C, with a warning at best.

The last line of output is the one overflow that is not a mistake. Unsigned arithmetic is defined to wrap round modulo 2⁶⁴, so the maximum plus one is exactly 0. Signed overflow has no such guarantee: a signed std::int64_t stops one bit short of the count, at 2⁶³ − 1, and going past it is undefined.

Without recursion, three pairs of towers

#include <array>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>

using Towers = std::array<std::vector<int>, 3>;

// Plays the one legal move between towers a and b, whichever way round it goes.
void move_between(Towers& towers, int a, int b) {
    if (towers[a].empty() || (!towers[b].empty() && towers[b].back() < towers[a].back())) {
        std::swap(a, b);
    }
    int disk = towers[a].back();
    towers[a].pop_back();
    towers[b].push_back(disk);
    std::cout << "Move disk " << disk << " from " << "ABC"[a] << " to " << "ABC"[b] << '\n';
}

void hanoi_pairs(int n) {
    Towers towers;
    for (int disk = n; disk >= 1; disk--) {
        towers[0].push_back(disk);
    }
    // The same three pairs of towers, over and over. For an odd n, B and C trade places.
    const int b = n % 2 == 0 ? 1 : 2;
    const int c = 3 - b;
    const std::uint64_t total = (std::uint64_t{1} << n) - 1;
    for (std::uint64_t m = 0; m < total; m++) {
        switch (m % 3) {
            case 0: move_between(towers, 0, b); break;
            case 1: move_between(towers, 0, c); break;
            case 2: move_between(towers, b, c); break;
        }
    }
}

int main() {
    hanoi_pairs(3);
}

g++ -std=c++17 hanoi_pairs.cpp -o hanoi_pairs
./hanoi_pairs

This loop never decides which disk to move. It cycles through three pairs of towers — A and B, A and C, B and C for an even number of disks, with B and C trading places for an odd number — and between any two towers there is exactly one legal move, which move_between finds by comparing their top disks and swapping a and b if the move goes the other way. The loop bound is a std::uint64_t for the reason the section above gives: (std::uint64_t{1} << n) - 1 is well defined up to 63 disks, where the signed (1LL << 63) - 1 would overflow.

Those three repeated pairs are the smallest disk’s circuit seen from the outside: every third move involves each pair, and the pattern reproduces the recursive solution exactly. The iterative solution shows why, move by move on a board.

The same algorithm in other languages

• Tower of Hanoi in PythonRecursive and iterative programs, why Python's recursion limit never bites here, and integers that simply do not overflow.
• 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#Top-level statements, an iterator whose moves LINQ can query, and ulong, checked arithmetic and UInt128 for the move count.

Frequently asked questions