Night falls over the archipelago. Your sloop is heavy with spice, and every island port keeps a lantern lit for you. Deliver to them all and sail home — the sea is calm, but every league costs you till dawn.
Chart all five voyages — the maps grow from five ports to eighteen — then a real optimizer charts them back at you.
Five voyages, five routing puzzles — here's your sailing next to the proven shortest rounds.
Visit every port exactly once and return home, sailing as little as possible. That is the Travelling Salesman Problem — the most famous puzzle in Operations Research, studied since the 1930s and still the benchmark every routing idea is tested against.
It looks innocent. It is anything but.
Your final voyage had 18 ports — that's 3.2 quadrillion distinct rounds (18!/2 = 3,201,186,852,864,000). Checking a billion every second would take 37 days; at 25 stops the list outgrows the stars in the observable universe. No list-them-all approach survives.
One honest clue does carry over: in the plane, a round that crosses itself can always be shortened by uncrossing two legs — which is why your chart warned you in red.
This game's optimizer never lists routes — it remembers partial answers instead. Held–Karp (1962) rests on one observation: the cheapest way to have visited a set of ports and be standing at port j doesn't depend on the order inside the set. So it fills a table over subsets:
C(S, j) = min over k ∈ S\{j} of
C(S\{j}, k) + d(k, j)
answer = min over j of
C(all ports, j) + d(j, harbor)
For 18 ports that's 218 subsets × 18 ends ≈ 4.7 million table entries instead of 3.2 quadrillion orders — filled in under a second, every entry exact. The result is a proof, not a good guess.
Held–Karp runs live in your browser (plain TypeScript in a Web Worker — no server, no baked answers). But its appetite doubles with every port: near 20 ports the table outgrows a phone's memory. Real fleets visit hundreds of stops, so industry changes tools — branch-and-cut solvers prove optimality into the tens of thousands of cities (Concorde's record: an 85,900-city tour, proven), and heuristics like 2-opt (your red-leg uncrossing, made systematic) or Lin–Kernighan deliver near-optimal tours for millions of stops — fast, but without the proof.
The same maths routes parcel vans, field-service technicians, waste-collection trucks — even the drill head etching a circuit board.
Use case: vehicle routing ▸ Follow me for more games ▸