Multi-threaded Towers of Hanoi with Air Traffic Control

Rings Speed

Moves: 0
Rings in the air: 0
Peak airborne: 0
Flight threads: 0
ATC holds: 0
Elapsed: 0.0 s

ATC radio

The classic problem

The Towers of Hanoi was introduced by the French mathematician Édouard Lucas in 1883. You have three towers and a stack of rings of different sizes, piled largest to smallest on the first tower. The goal is to move the whole stack to another tower, following three rules:

Move only one ring at a time.
Only the top ring on a tower can be moved.
A larger ring may never be placed on top of a smaller one.

The solution is a textbook example of recursion. To move n rings from A to C, move the top n − 1 rings out of the way to B, move the largest ring to C, then move the n − 1 rings from B onto it. The minimum is 2ⁿ − 1 moves, so 10 rings take 1,023 moves. The legend says monks moving 64 golden rings will end the world when they finish. At one move per second, that would take about 585 billion years.

function solve(n, from, to, via) {
  if (n === 0) return;
  solve(n - 1, from, via, to);   // clear the way
  move(n, from, to);             // move the largest ring
  solve(n - 1, via, to, from);   // stack the rest back on top
}

This version follows the same recursive move list, in the same order, and every ring lands legally. The difference is that a ring doesn't wait for the previous ring to land before taking off, so flights overlap in the air.

A 1995 story

In 1995, Jim Conning wrote and submitted this program as an entry in the Java Contest that commemorated the launch of Java 1.0. It was a Java applet that ran right in the browser, with each ring flying on its own Thread and air traffic control keeping them from colliding.

Sadly, it stopped working when Java 1.1 came out, because that release blocked Thread.sleep() for security reasons, and the applet's animation depended on it. The author never updated it to work without Thread.sleep(), and the source code was lost. GitHub hadn't been invented yet in 1995.

This page is a re-creation, built with the browser's own threads more than thirty years later. Its code was designed and implemented by Claude Opus 5.5.

How it's built

The stack

Plain HTML, CSS and JavaScript. There's no framework, no build step and no dependencies: just index.html, styles.css and hanoi.js. It runs on any static host, or by opening index.html from disk.
HTML5 Canvas draws the towers and rings, redrawn every frame with requestAnimationFrame.
Web Workers provide the threads. Each one is a real operating-system thread with its own event loop and no shared memory. Threads talk to the main thread only by passing messages.

Who does what

Solver (main thread): The recursive function above produces the full list of 2ⁿ − 1 moves.
Dispatcher (main thread): Starts a new flight thread for each move, in order, keeping up to six alive at once. A thread can be started before its ring is free; it simply waits until ATC clears it to move.
Flight threads (one Web Worker per move): Each worker flies a single ring along its route: up its tower, across the cruise lane, down onto the destination tower. It only ever flies as far as ATC has cleared it, and hovers when it reaches the end of its clearance. It animates itself with await sleep(16), a timer-based pause that hands the thread back to its event loop instead of blocking it. That's the modern replacement for the Thread.sleep() call that broke the 1995 applet. The worker reports its position about 60 times a second.
Air Traffic Control (main thread): Owns the airspace. Every time any ring reports a new position, ATC recalculates how far each flight may go and radios out extended clearances. Because all workers report to this one place, no locks are needed: the main thread handles one message at a time.
Renderer (main thread): Draws the towers, the cruise lane and the latest reported position of every ring.

Airspace reservations

Before anything flies, the solver's move list is replayed once so every move knows its exact route: straight up from its spot on the stack, along the cruise lane, and straight down to the exact height it will land at. Each route is three straight legs, so the airspace a ring still needs, from where it is now to where it will land, is just three rectangles the width and height of the ring.

The rule ATC enforces is simple: a ring may never enter airspace still owned by an earlier move. ATC walks each ring's route forward from its current position and clears it up to the exact point where it would come within a few pixels of an earlier ring's remaining airspace. A ring therefore flies right up to the edge of the airspace ahead of it and stops there, drawn with a pulsing amber outline and reported on the ATC radio. As the ring ahead moves on, its airspace shrinks behind it and the follower's clearance extends, so rings trail each other closely up the tower, along the lane and down onto the stack.

Why rings can't collide, cross out of order or deadlock

No collisions. A later ring is never cleared into an earlier ring's remaining airspace, and an earlier ring's route never runs through a later ring, because the later ring was never allowed in. Reservations only shrink as rings fly, so a clearance stays safe even if it arrives a few milliseconds late.
Correct stacking. A ring's remaining airspace ends at the exact spot it will land. Any later ring that would take off from beneath it, or land on top of it, is held until it has moved on, so every tower sees exactly the sequence the recursive algorithm produced, even though the flights overlap.
No deadlock. Rings only ever wait for earlier moves, never later ones. The earliest unfinished move has nothing ahead of it, so it can always fly, and everything behind it eventually gets its turn.

Why message passing instead of shared memory

Java-style locks (SharedArrayBuffer with Atomics.wait) only work in the browser when the server sends special cross-origin isolation headers. Most static hosts can't send them, and neither can a file opened from disk. Message passing to a single controller works everywhere. It's also closer to how real air traffic control works: pilots radio the tower and wait for clearance.