All 100 county seats
North Carolina has 100 counties, and every one has a county seat, from Murphy in the far west to Manteo on the Outer Banks. Suppose you had to visit all of them and come home. Which order?
It sounds like an afternoon with a map. It is one of the most famous hard problems in computing.
Scroll ↓
One hundred dots
Each dot is a county seat, placed at its real latitude and longitude. Nobody drew the outline of the state. The towns draw it by themselves.
How many routes are there?
Start in Raleigh. There are 99 choices for the first stop, 98 for the next, and so on down to one. Halve it, because a loop driven backwards is the same loop. Here is the exact number of different round trips:
That is digits. The usual estimate for the number of atoms in the observable universe has 81.
So just check them all?
Give a computer a billion routes a second, which is generous. Checking every route would take about years. The universe is about 13.8 billion years old.
No computer that will ever exist does this by brute force. So nobody tries. They cheat, cleverly.
Cheat one: always go to the nearest town
From Raleigh, drive to the closest county seat you have not visited. Repeat. It is what most people would do with a paper map. Keep scrolling and watch it go.
It works, mostly. But watch the end: having picked off everything nearby, it is left with stragglers, and it has to make long jumps back across the state to collect them.
A route. Not a good one.
Nearest-town-next gives a full loop of . Look for the places where the line crosses itself. A route that crosses itself can always be made shorter, by uncrossing it.
Cheat two: untangle it
Take any two legs of the trip. Reverse the stretch between them, and keep the change if the loop got shorter. Do that again, and again, until no swap helps. It is called 2-opt, and it dates from 1958.
Scroll, and the route untangles one swap at a time.
, in well under a second
The untangled route is shorter than the first one, and the computer took swaps to get there. It is not provably the best of the 156-digit pile. It is very good, and it exists now.
That trade is the whole lesson. A perfect answer you can never compute is worth less than a good answer you have in time to use.
Why a business should care
Delivery routes, the walk a picker takes through a warehouse, the order jobs run through a machine. Each is this problem in different clothes, and each grows as fast as the county count did. Ten deliveries have 181,440 possible round trips. Twenty have more than sixty quadrillion.
People handle these with experience and habit, and experience is good. It is also nearest-town-next, and you have just watched what that leaves on the table.
Try another start
Sources and method. County seats are from Wikipedia's list of North Carolina counties. Coordinates are the U.S. Census Bureau's 2024 Gazetteer internal point for each town, except Currituck, which is unincorporated and has no Census place record; its coordinates come from its Wikipedia article. Distances are straight-line great-circle miles, not road miles, so a real drive is longer. The route is nearest-neighbour followed by 2-opt, run in your browser as you watch; it finds a very good loop, not a proven optimum. The 1080 atoms figure is the commonly quoted rough estimate. Highland Willow, 2026-10-29.
More pieces like this
- Where an Order Spends Its Time: one order, quote to invoice, at one pixel per minute.
- If a CPU Cycle Took One Second: computer waiting times rescaled until one processor cycle lasts a second.
- Throwing Darts at Pi: Monte Carlo Simulation: Monte Carlo simulation, from pi to whether an order ships on time.
- Your Spreadsheet as a City: one bad formula in a quoting workbook, and how far the damage travels.
- Seven Years to a Fraser Fir: one acre of Christmas trees and the cash it holds before anything sells.
- Murphy to Manteo, to Scale: North Carolina at one mile to 40 pixels, elevation, counties and economy.