Tower of Hanoi in Java

Run it yourself

Save the listing as Hanoi.java. On Java 10 or older, compile it first with javac Hanoi.java and then run the class with java Hanoi. Since Java 11 the launcher does both in one step for a single source file, which is all this program needs:

java Hanoi.java

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

import java.math.BigInteger;

public class CountMoves {
    public static void main(String[] args) {
        // Java uses only the low six bits of a long shift distance, so this is 1L << 0.
        long shifted = (1L << 64) - 1;
        System.out.println("(1L << 64) - 1      = " + shifted);

        // 2^64 does not fit in a long, so the cast pins it to Long.MAX_VALUE first.
        long rounded = (long) Math.pow(2, 64) - 1;
        System.out.println("Math.pow(2, 64) - 1 = " + rounded);

        // BigInteger has no ceiling.
        BigInteger exact = BigInteger.ONE.shiftLeft(64).subtract(BigInteger.ONE);
        System.out.println("BigInteger          = " + exact);

        // Or keep all 64 bits in a long and print them as unsigned.
        System.out.println("unsigned long       = " + Long.toUnsignedString(-1L));
    }
}

java CountMoves.java

(1L << 64) - 1      = 0
Math.pow(2, 64) - 1 = 9223372036854775806
BigInteger          = 18446744073709551615
unsigned long       = 18446744073709551615

Java’s long is a signed 64-bit integer, so its largest value is 2⁶³ − 1: one bit short of the 64-disk move count. The two obvious ways to write 2⁶⁴ − 1 both fail, and neither complains.

• (1L << 64) - 1 is 0. 1L << 64 is not the huge power of two it looks like: Java uses only the lowest six bits of the shift distance for a long, so shifting by 64 is shifting by 0, and the result is 1.
• Math.pow(2, 64) cast to a long, minus one, is 2⁶³ − 2. Math.pow gets the size right but returns a double, and a double too large for a long is pinned to Long.MAX_VALUE by the cast — off by nine quintillion.

Two things work:

• BigInteger, which has no upper limit and gives the exact value.
• Long.toUnsignedString(-1L). A long already has the right 64 bits in it if you stop reading them as signed: -1L is all ones, which is 2⁶⁴ − 1 as an unsigned number, and Long.toUnsignedString prints it that way.

C# has the type Java leaves out: ulong, an unsigned 64-bit integer whose maximum is the move count itself.

Without recursion, using an explicit stack

import java.util.ArrayDeque;
import java.util.Deque;

public class HanoiStack {
    // A job still to do: move n disks, or, when single is true, move just disk n.
    record Job(int n, char source, char target, char spare, boolean single) {}

    static void hanoi(int disks, char source, char target, char spare) {
        Deque<Job> jobs = new ArrayDeque<>();
        jobs.push(new Job(disks, source, target, spare, false));

        while (!jobs.isEmpty()) {
            Job job = jobs.pop();
            if (job.single()) {
                System.out.println("Move disk " + job.n() + " from " + job.source() + " to " + job.target());
            } else if (job.n() > 0) {
                // Pushed in reverse: a stack hands back the last thing pushed first.
                jobs.push(new Job(job.n() - 1, job.spare(), job.target(), job.source(), false));
                jobs.push(new Job(job.n(), job.source(), job.target(), job.spare(), true));
                jobs.push(new Job(job.n() - 1, job.source(), job.spare(), job.target(), false));
            }
        }
    }

    public static void main(String[] args) {
        hanoi(3, 'A', 'C', 'B');
    }
}

java HanoiStack.java

Recursion is a stack you do not have to manage. This version manages it. Each entry on the ArrayDeque is a job still to do: move n disks, or, when single is true, move disk n by itself. Popping a transfer of n disks pushes its three parts back on — the second transfer, the single move, the first transfer — in reverse, because a stack hands back the last thing pushed first. The loop ends when there is nothing left to do.

It prints the same seven lines as the recursive program. This is the mechanical way to turn any recursive function into a loop, and it makes the call stack from the trace at the top of the page into an ordinary data structure you can inspect. record needs Java 16 or newer; on older versions, a small static class with the same five fields does the same job.

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 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