“Find the shortest route” can describe several different problems. You may need a path from one point to another, a route that visits every waypoint once, or a closed tour that returns to the start. Obstacles, one-way links and repeated visits can change the rules again.
Before optimising anything, define what a valid route is.
Path, visit-all route or tour?
A shortest-path problem usually asks for the least-cost path between specified endpoints in a network.
The travelling salesperson problem asks for a shortest tour that visits every listed location and returns to its start, given travel costs between locations.
A puzzle game may borrow parts of either idea without matching the formal problem. It might not require a return, might use a board with obstacles, or might score distance relative to an internal target. Do not attach the TSP label until the rules genuinely fit.
Step 1: build a quick candidate
Nearest neighbour is a simple heuristic:
- Start at the required point.
- Visit the closest unvisited point.
- Repeat until every required point is included.
- Return to the start only if the rules require a tour.
This is fast and gives you something concrete to improve. It is not a proof. A cheap-looking move now can leave an isolated point that forces a long journey later.
Try more than one starting point when the rules allow it, or deliberately compare the two closest choices at an early branch. A small change near the start can alter the expensive final connection.
Step 2: scan for crossings
In an ordinary complete Euclidean tour—straight-line distance between points, no obstacles and any point connectable to any other—an optimal tour does not need crossed edges. If edges AB and CD cross, reconnecting the endpoints without the crossing gives a shorter pairing under the usual geometric conditions.
That makes a crossing a useful repair signal. Cut the two crossed edges, reconnect the route in the valid uncrossed way, and compare total length.
The rule has boundaries. Roads may be one-way, barriers may block the uncrossed connection, and costs may not equal straight-line distance. In those settings, the picture alone is not enough.
Step 3: try local edge swaps
A common improvement move is a two-edge swap, often called 2-opt:
- Remove two route edges.
- Reverse the segment between them if needed.
- Reconnect to form a valid route or tour.
- Keep the change only if total permitted cost falls.
Repeat until no tested swap helps. This can remove crossings and repair other local detours.
Reaching a local optimum means no move in your chosen neighbourhood improved the route. It does not mean no entirely different route is shorter.
Step 4: compare and bound
Record route length rather than judging by appearance. Then ask:
- What alternative early choice have I not tested?
- Is one long edge forced by an outlying point?
- Can I establish a lower bound that no valid route can beat?
- For a small puzzle, can I enumerate every permitted order?
Exhaustive comparison grows rapidly as locations are added. More advanced exact methods use dynamic programming, branch-and-bound or specialised solvers to rule out shorter alternatives. A heuristic earns the label “best found”, not “proved shortest”, unless an exact certificate or complete argument supports it.
What no crossing does—and does not—tell you
Removing a crossing can certify a local improvement in the Euclidean setting. A final route with no crossings has passed that particular test.
It has not passed every test. Two crossing-free tours can have different lengths, and a sequence of local swaps can stop before the global optimum. This distinction is the central honesty rule for route puzzles.
Constraint reasoning appears in shape puzzles too. In polyomino puzzles, a plausible local placement can block a global solution in the same way that a tempting short edge can create an expensive route ending.
Math & Patterns lists Path Finder, described as visiting waypoints while controlling route distance. Its page is an app-only next step, and this article does not claim that its internal score certifies a mathematical optimum or that every level is a travelling-salesperson instance.
Sources and further reading
- OpenStax’s travelling salesperson chapter introduces the tour problem and common heuristics.
- The Computer Science Field Guide explains the travelling salesperson problem and computational tractability.
- NIST’s Dictionary of Algorithms and Data Structures gives a concise travelling salesperson definition.
- A recent paper on Euclidean TSP structure provides formal context for geometric tour properties.
