Tower of Hanoi in C#

Run it yourself

dotnet new console creates a project whose Program.cs already uses top-level statements, so paste the listing over that file's contents as it is. Top-level statements need C# 9, which means .NET 5 or later; the console template has produced them by default since .NET 6:

dotnet new console -o Hanoi
cd Hanoi
# replace Program.cs with the listing, then:
dotnet run

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.

Counting the moves

using System;
using System.Numerics;

// ulong is unsigned 64-bit: 2^64 - 1 is exactly its largest value.
ulong moves = ulong.MaxValue;
Console.WriteLine($"ulong:      {moves}");

// By default, arithmetic that overflows wraps round silently...
ulong wrapped = moves + 1;
Console.WriteLine($"wrapped:    {wrapped}");

// ...unless you ask for it to be checked.
try
{
    ulong next = checked(moves + 1);
    Console.WriteLine($"checked:    {next}");
}
catch (OverflowException)
{
    Console.WriteLine("checked:    OverflowException");
}

// UInt128, since .NET 7, is twice as wide: its maximum is the 128-disk count.
Console.WriteLine($"UInt128:    {UInt128.MaxValue}");

// BigInteger has no ceiling at all.
Console.WriteLine($"BigInteger: {BigInteger.Pow(2, 64) - 1}");

# in the same project, paste over Program.cs, then:
dotnet run

ulong:      18446744073709551615
wrapped:    0
checked:    OverflowException
UInt128:    340282366920938463463374607431768211455
BigInteger: 18446744073709551615

ulong is an unsigned 64-bit integer, and its maximum, ulong.MaxValue, is exactly 2⁶⁴ − 1: the 64-disk move count fits with not one value to spare. Java has no such type, which is why the obvious way to write the count there quietly prints 0.

What happens one past it depends on context. C# arithmetic is unchecked by default, so moves + 1 silently wraps round to 0. Inside checked(...) the same addition throws an OverflowException instead. To make that the rule for a whole project, set <CheckForOverflowUnderflow>true</CheckForOverflowUnderflow> in the .csproj.

Past 64 disks there are two ways on. UInt128, added in .NET 7, is an ordinary value type twice as wide, and its maximum is the 128-disk move count exactly. BigInteger, in System.Numerics, has no upper limit at all.

Moves on demand, queried with LINQ

using System;
using System.Collections.Generic;

foreach (var (disk, fromPeg, toPeg) in Hanoi(3, 'A', 'C', 'B'))
{
    Console.WriteLine($"Move disk {disk} from {fromPeg} to {toPeg}");
}

// An iterator: each move is produced only when the loop above asks for the next one.
static IEnumerable<(int Disk, char From, char To)> Hanoi(int n, char source, char target, char spare)
{
    if (n == 0)
    {
        yield break;
    }
    foreach (var move in Hanoi(n - 1, source, spare, target))
    {
        yield return move;
    }
    yield return (n, source, target);
    foreach (var move in Hanoi(n - 1, spare, target, source))
    {
        yield return move;
    }
}

# in the same project, paste over Program.cs, then:
dotnet run

yield return turns Hanoi into an iterator. Calling it runs none of its body; each time the foreach asks for the next move, the method runs just far enough to produce one, and yield break ends a call with nothing to give. The moves are named tuples, (int Disk, char From, char To), and the foreach takes each one apart with deconstruction.

The two inner foreach loops are the part C# makes you write out. A JavaScript generator hands a whole nested generator on with yield*; C# has no equivalent, so every move a smaller call produces is yielded again by hand, once for each call it passes through on the way up. A move therefore costs work proportional to the depth of the call that made it, and every call builds an iterator object of its own — fifteen of them for three disks, 2ⁿ⁺¹ − 1 in general. At any size you could watch, that is too little to notice.

What C# gives back for that is LINQ. The moves are an IEnumerable, so every LINQ operator works on the solution without storing it, and each runs the iterator only as far as it needs to. For ten disks, Hanoi(10, 'A', 'C', 'B') answers:

• .Count() is 1,023 — every move, 2¹⁰ − 1 of them.
• .Count(m => m.Disk == 1) is 512: the smallest disk makes half of all the moves, one on every odd-numbered move.
• .Count(m => m.Disk == 10) is 1: the largest disk crosses once.
• .TakeWhile(m => m.Disk != 10).Count() + 1 is 512, so that crossing is move 2⁹ — the exact middle of the solution.

Those are facts the algorithm page proves, checked here by asking the moves rather than reading 1,023 lines of them. And .First(m => m.Disk == 10) returns (10, A, C) having produced only the 512 moves up to it: the iterator is simply never asked for the rest.

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++Collecting the moves in a std::vector, the 64-disk count checked by the compiler, and three pairs of towers in a loop.

Frequently asked questions