Travelling Salesman Problem Generator
A handful of cities on a grid, and the shortest round trip that visits each once. This is the standard example of a problem where checking an answer is easy and finding one is not — and where a sensible-looking rule, always go to the nearest city you have not visited yet, produces a tour that is usually close and reliably not best. Each instance here is solved exactly, so the gap between the two is a measured number rather than an assertion.
What this generator does
Places cities at random integer coordinates, builds the symmetric distance matrix, and finds the shortest tour exactly with the Held-Karp dynamic programme. It also runs the nearest-neighbour heuristic and reports how much worse that tour is, as a percentage.
How to use this tool
- Choose how many cities the instance should have.
- Find the shortest tour you can, starting and ending at the first city.
- Reveal the optimal tour and its length.
- Compare against the nearest-neighbour tour shown alongside.
Understanding the controls
- How many cities
- Between 4 and 10. Ten is the ceiling because the exact solver's cost grows as the number of cities squared times two to the number of cities.
- Seed
- Reproduces the same coordinates, so an instance can be set as an exercise and solved independently.
- Show the answer
- Reveals the optimal tour in order, its length, and the nearest-neighbour length beside it.
Common use cases
- Practice instances with a proved optimum to check an attempt against
- Showing how much the nearest-neighbour rule actually costs on real instances
- Testing a tour-finding implementation against exact answers
- Teaching why exact methods stop scaling, using the city limit as the illustration
- Setting the same instance to a group from a seed
How this generator works
Held-Karp builds up the shortest path that starts at the first city, visits a given subset, and ends at a given city, one subset at a time. That is exponential but far better than trying every tour, and at ten cities it is instantaneous. The tests check it against exhaustive enumeration at up to eight cities.
Randomness and fairness
The city coordinates are random; the optimal tour is computed exactly from them. Seeded instances reproduce and are therefore explicitly not cryptographically secure. Unseeded, the browser's cryptographically secure generator places the cities.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- Ten cities is the ceiling. The problem is genuinely hard, and going further needs a different class of solver.
- Distances are straight-line between coordinates, so this is not road distance or travel time.
- The instance is symmetric — the distance from A to B equals B to A — which is not true of one-way systems.
- No map is drawn; cities are given as coordinates.
- Instances are not saved, so seed one you want to set again.
Privacy and your data
Coordinates and tours are generated and solved in your browser. Nothing is transmitted, and nothing survives the visit.
Related generators
- Knapsack Problem Generator0/1 knapsack instances solved exactly by dynamic programming, with the value-per-weight answer shown alongside for comparison.
- Hamiltonian Path Challenge GeneratorGraphs where the puzzle is to visit every node exactly once, with every such path counted by exhaustive search.
- Maze GeneratorPrint a maze with exactly one route from start to finish — three textures from long corridors to short dead ends, any size up to 40 by 40.
- Makespan Scheduling Problem GeneratorJobs across identical machines, scheduled longest-first, with two lower bounds that often prove the schedule optimal.
- Bin Packing Problem GeneratorPacking instances with bins of one size or several at different prices, each with an answer, a lower bound, and a plain statement of when the two meet.