What exactly makes the travelling salesman problem hard, given that checking a route is trivial?

The clearest way to see what goes wrong with the nearest-city heuristic is that it is forced to pay for its own convenience at the end.

At every step it takes the cheapest available hop. That is locally sensible and it leaves behind a set of cities that are far from each other and far from where you now are — precisely the ones it kept skipping because something closer was available. The final legs of the tour are then enormous, and they cost more than everything the greedy choices saved.

You can construct arrangements where this is arbitrarily bad, and the constructions are not contrived: a line of closely spaced cities with one outlier does it. The greedy route runs happily down the line and then has to cross the whole map twice.

The general principle is that the cost of a decision in this problem is not visible when the decision is made. Any method that commits early without accounting for what it leaves behind can be defeated.

The structural answer is that the problem has no useful local structure to exploit.

Compare it with something easy. Finding the shortest path between two points on a network is easy because of a property that makes the whole thing collapse: any sub-path of a shortest path is itself a shortest path. That lets you build the answer from smaller answers and never revisit.

The salesman problem has no equivalent property. A tour that visits a subset of cities optimally may not appear in the optimal full tour at all, because the full tour has to enter and leave that subset at particular points, and those entry and exit choices change what the best sub-tour is. Optimal pieces do not assemble into an optimal whole.

Once that fails, you have lost the technique that makes essentially every easy optimisation problem easy, and what remains is search over a space of routes that grows faster than exponentially with the number of cities.

Worth adding a corrective, because "NP-hard" gets read as "unsolvable" and it is not remotely the case in practice.

Instances with tens of thousands of cities are routinely solved to proven optimality with modern solvers, and good heuristics get within a couple of percent of optimal on enormous instances in seconds. The theoretical hardness is a statement about worst cases as size grows without bound, not a claim that your particular instance is out of reach.

What the hardness does tell you is where to spend effort: there is no point looking for a clever exact formula, and there is a great deal of point in using an established solver, or in accepting a near-optimal answer. For nearly every real routing problem, two percent from optimal delivered in a second beats optimal delivered next week.

One intuition pump that helped me: try to find the optimal tour for fifteen randomly placed points by hand, on paper, and then try to prove to somebody that your answer is optimal.

Finding a good tour is easy — your eye does it. Proving no better one exists is where the difficulty lives, and doing it once by hand makes the theory feel obvious rather than abstract. That gap between "I found a good answer" and "I can rule out every better one" is the entire subject.