Shortest Route Puzzles: How to Find the Fewest Steps by Hand

To solve a shortest route puzzle, spread outward from the start: give the start a distance of zero, then keep settling whichever unsettled place is nearest, writing its best distance beside it and updating its neighbours. When the goal is settled, its label is the answer, and tracing the labels backwards from the goal gives you the route itself.

The same idea works on a map of roads with different lengths and on a board where every move counts as one step. This guide walks through the method by hand, a full worked map, a board example with a chess rook, a quick check for goals that can never be reached, and a practice puzzle with its answer.

What is a shortest route puzzle?

A shortest route puzzle gives you places joined by connections and asks for the cheapest way from a start to a goal. The cost can take two forms.

• Lowest total. Each road has a length, a travel time or a price, and you want the smallest sum.
• Fewest steps. Every move costs the same, so you simply want the smallest number of moves. Board puzzles with a moving piece usually work this way.

The puzzle may be drawn as a map, written as a list of roads, or set on a grid of squares. Underneath, it is always the same thing: dots for places, lines for connections and a number on each line.

Why is the route with the fewest roads not always the shortest?

This is a common trap. A route that looks direct may use one very long road, while a route that wanders through more places can add up to less.

It is easy to be drawn to routes with few turns. The numbers are what count. That is why guessing can fail, and why a method that checks every place in a fixed order is worth learning. The worked example below contains exactly this trap.

How does spreading outward from the start work?

The method grows a circle of certainty around the start. Places inside it have their final, best distance. Places on its edge have a best guess so far. Each round, the nearest guess on the edge becomes certain.

1. Label the start with zero and mark it settled.
2. Update its neighbours. For each road leaving the place you just settled, add the road length to that place's label. If the result beats the neighbour's current guess, write the new number and note where it came from.
3. Settle the nearest guess. Look at every unsettled place that has a guess and pick the smallest. Mark it settled. Its number will never improve again.
4. Repeat steps two and three until the goal is settled.
5. Trace back. From the goal, follow the notes of where each best number came from, all the way back to the start. That chain is the shortest route.

Why can the nearest guess never improve? Every road length is zero or more, so any other way of reaching that place would have to pass through a place that is already further away. It cannot come out cheaper.

How does the method solve a worked example?

Here is an original map. You travel from the start S to the goal G through the places A, B, C, D and E. Every road can be used in both directions.

Before reading on, try a guess. The route S, B, D, G looks the most direct, because it uses only three roads. Its total is 2 plus 10 plus 3, which is 15.

Now apply the method round by round.

Trace back. G got its best label from D. D got its best from C, C from A, A from B and B from S. The shortest route is S, B, A, C, D, G, with a total length of 14.

Notice round two. The direct road from S to A has length 4, but going through B first costs only 2 plus 1. Small roads that cut a corner like this are one frequent reason a guess goes wrong.

A computer check lists every route from S to G that never visits a place twice. Only S, B, A, C, D, G reaches 14, and three different routes tie in second place at 15, including the three-road route S, B, D, G.

How do you count moves on a board?

On a board, every move costs one step, so the method becomes simpler. Instead of comparing totals, you label squares in rings: the start is zero, everything one move away is one, everything one move from those is two, and so on. The first ring that reaches the goal gives the answer.

A rook in chess makes a good test piece. According to a paper published on 7 December 2021, a rook may travel as far as it likes in a straight line across its row or up and down its column, yet it can never leap a piece standing in its way ^[1].

The same paper defines the distance between two squares as the length of the shortest route between them, and the diameter of a board as the largest of those distances over every pair of squares ^[1].

With nothing else on the board, two moves are always enough for a rook or a queen to get from any square to any other, the paper notes ^[1]. It also shows that, on any square board of at least three by three, one blocking piece on a square other than a corner raises the rook's diameter to three, while a blocker in a corner leaves it at two ^[1].

That last fact is a useful warning for puzzle solvers. A single blocked square in the middle of the board is enough to make some trips longer, so you cannot assume every answer is small.

How does the board example work?

Take a five by five board. Columns are a to e from left to right, and rows are 1 to 5 from bottom to top. A rook starts at a1, the bottom left corner, and must reach e5, the top right corner. Four squares are blocked: d5, c4, e3 and d2. The rook may not stop on or pass through a blocked square.

Labelling in rings gives this table, with the fewest moves needed to reach each square and X for a blocked square.

The goal e5 needs five moves. Reading the labels backwards, e5 can only be reached in time from e4, e4 from d4, d4 from d3, d3 from a3, and a3 from a1. So the route is a1, a3, d3, d4, e4, e5, and a full search confirms it is the only five-move route.

Notice how badly the obvious routes fail. Sliding along the bottom row to e1 takes one move, but e3 then blocks the column. Sliding up column a to a5 also takes one move, but d5 blocks the top row. The blockers turn a corner-to-corner trip that would take two moves on an empty board into a five-move puzzle.

How can you tell a goal can never be reached?

Before you search, it is worth asking whether the goal can be reached at all. Some move rules lock a piece into a fixed set of positions.

A paper published on 15 March 2010 studies routes that visit every point of a numbered line once, using hops of length one, two and three ^[2]. One of its results says that no route can visit every point of such a line exactly once when it has one hop of length two and every other hop is of length three ^[2].

In the reasoning behind that result, the paper points out that a route opening with a hop of two and then using only hops of three reaches only points that leave the same remainder when divided by three ^[2]. The same kind of lock holds for any piece whose moves all have one fixed size.

Here is how that idea helps on a puzzle. Imagine a row of ten stones numbered from zero to nine, and a counter on stone zero that may only hop exactly three stones left or right. It can land on zero, three, six and nine, and nowhere else. Asking for the shortest way to stone seven is a trick question: the answer is that there is none.

Look for this kind of lock whenever every move changes position by the same amount. If the start and the goal sit in different locked groups, stop searching.

Which method should you use?

On a very small map, listing every route is fine. As maps grow, the number of routes explodes, while spreading outward only ever handles each place once.

What are the most common mistakes?

• Trusting the route with the fewest roads. Always add up the lengths.
• Settling a place too early. Only settle the smallest label among all unsettled places, not just the newest one.
• Forgetting to note where each label came from. Without those notes you know the distance but not the route.
• Letting a rook pass through a blocked square. Check every square along a slide, not just where it ends.
• Searching for an impossible goal. Check reachability first when every move has a fixed size.

Can you solve this practice puzzle?

Travel from P to W. Every road can be used in both directions.

What is the shortest total, and which route gives it? Settle the places in order and keep notes of where each label came from.

What is the answer?

The shortest total is 16, by the route P, Q, R, T, U, W.

Settling in order gives Q at 3, then R at 5, because P to Q to R costs 3 plus 2, which beats the direct road of 6. Next comes T at 9, through R. Then U settles at 11, through T, which beats the direct road from R at 14. Last, V and W both reach 16: V through T, and W through U.

The route P, Q, R, T, V, W comes to 17, and so do several other routes. A computer check of every route confirms that 16 is reached in only one way.

Ready for a live shortest route puzzle? This riddle asks for the fewest days needed to travel from one gate to another. Spread outward from the start, settle the nearest place each round and see whether your labels lead you to the answer.