How to Solve Pair-Matching Path Puzzles: Join Every Pair

To solve a pair-matching path puzzle, start in the corners and along the edges, where empty cells have so few neighbours that the path through them is forced. Then use the rule that every cell must be filled: any empty cell that only one path can still reach belongs to that path, and the forced moves chain together until every pair is joined.

Below are the rules, four forcing patterns, one puzzle solved in nine short steps and a six by six grid to try, answer included.

What is a pair-matching path puzzle?

A pair-matching path puzzle is a square grid with a few numbers in it. Each number appears exactly twice. Your job is to join every pair of equal numbers with a path that moves from cell to neighbouring cell, up, down, left or right, never diagonally.

Paths may bend as often as they like, but two paths can never cross or share a cell. A path may run right beside its own earlier cells, though: the only things forbidden are crossing and sharing. In the version this guide uses, every cell in the grid must belong to some path when you finish. A well-made puzzle has exactly one solution.

Why does the every-cell rule matter so much?

Without it, a pair can be joined in several ways, and a puzzle could have more than one answer. With it, every empty cell becomes a small clue of its own, because something has to pass through it.

That gives you the two facts behind the deductions in this guide. Both are about route neighbours: the cell just before and the cell just after a given cell as you walk along its path.

• A cell in the middle of a path has exactly two route neighbours, the cell it is entered from and the cell it leaves by.
• A numbered cell is an end of its path, so it has exactly one route neighbour, the first cell of the route.

Route neighbours are not the same as every touching cell of the same number. Because a path may fold back beside itself, a cell can touch three cells of its own path while only two of them come right before and after it on the route.

An empty corner cell has only two neighbours in the whole grid. Since it must sit in the middle of some path, both of them must be its route neighbours, and the path runs through the corner from one to the other. This one idea is a good place to start any puzzle.

Which forcing patterns should you look for?

Four patterns are worth learning. The table compares them.

Empty corner works on the edges too, once a few cells are filled. Any empty cell left with exactly two free or usable neighbours behaves like a corner.

One way out is the simplest move. Extend a path from one of its numbers. Whenever only one neighbouring cell is free, step into it and look again.

Dead pocket is a test. If a move would leave an empty cell walled in by paths it cannot join, that move breaks the every-cell rule.

Single visitor finishes puzzles. Look at an empty cell and ask which path could pass through it, entering from one neighbour and leaving by another. If only one number qualifies, the cell is settled.

What is the step-by-step method?

1. Mark the corners. For each empty corner, note which two cells must be joined through it.
2. Run the edges. Check whether a path that starts on the border is forced to hug it, because cells beside the border have few ways in.
3. Follow forced paths. Extend any path end that has only one way out, and repeat after every new cell.
4. Test the doubtful moves. When a path end has two choices, check whether one of them strands a cell. If it does, take the other.
5. Fill the last cells by visitor. Ask which path can pass through each remaining empty cell.
6. Check the whole grid. Every cell used, every pair joined, no crossings.

How do the patterns crack a five by five path puzzle?

Here is an original puzzle with four pairs. Row 1 is the top row and column 1 is on the left.

We checked by computer, trying every possible set of routes, that exactly one solution uses every cell. Try it yourself first.

Step 1: the bottom left corner. Row 5, column 1 is empty and has only two neighbours: the 3 above it and row 5, column 2. So path 3 leaves its number in row 4, runs down into the corner and turns right into row 5, column 2.

Step 2: one way out. From row 5, column 2, the cell above is the 4 in row 4, which belongs to another path. The only way on is right, into row 5, column 3.

Step 3: avoid a dead end. From row 5, column 3, path 3 could go up into row 4, column 3. But that cell is boxed in by the 1, the 4 and the other 1, so path 3 could never leave it. Path 3 continues right into row 5, column 4.

Step 4: the bottom right corner. Above row 5, column 4 is a 1, so path 3 moves on into the corner at row 5, column 5. The corner forces it up into row 4, column 5.

Step 5: up the right edge. Row 4, column 4 holds a 1, so path 3 goes up to row 3, column 5. Row 3, column 4 holds a 2, so it goes up again to row 2, column 5.

Step 6: the top right corner. The corner at row 1, column 5 must join its two neighbours, row 1, column 4 and row 2, column 5. If path 3 turned left at row 2, column 5, that cell would use its two route neighbours on row 3, column 5 and row 2, column 4. It could not also link to the corner, and the corner would be left with only one usable neighbour.

So path 3 goes up into the corner, left to row 1, column 4 and reaches its other 3. Path 3 is complete.

Step 7: single visitor. Row 2, column 4 is now surrounded by path 3 on two sides and by the two ends of path 2 on the others. Only path 2 can pass through it, so path 2 runs from the 2 in row 2 through this cell to the 2 in row 3.

Step 8: single visitor again. Row 4, column 3 touches both ends of path 1, the 4 in row 4 and finished path 3. Only path 1 can enter and leave it, so path 1 runs from the 1 in row 3 down through it to the 1 in row 4.

Step 9: path 4. Five empty cells remain in the top left, and path 4 must use them all. The corner at row 1, column 1 forces the route through row 1, column 2 and row 2, column 1. The finished path runs from the 4 in row 2 up and around the corner, down column 1 to row 3, one cell right, and down into the 4 in row 4.

Here is the solution, with every cell showing the number of its path.

Notice that on an empty grid the two 3s would be only five steps apart, yet their path takes eleven steps round the edge of the grid. Do not assume the shortest route is the right one.

The solution also shows a path running beside itself. The 4 in row 2, column 2 touches three other cells of path 4, but only one of them, row 1, column 2, is its route neighbour. The route simply folds back around the corner and passes it again on the way down.

What does a paper on blocked chessboards show?

Mathematicians describe a grid like this as a network: each cell is a point, and neighbouring cells are joined by links. A paper published on 7 December 2021 defines a path in such a network as a walk whose points are all different, and the distance between two points as the length of the shortest path between them ^[1].

That paper looks at chessboards with blocking pieces on some squares ^[1]. With no blockers at all, a rook standing alone needs at most two moves to get from its square to any other ^[1]. It then asks how few blocking pieces are needed before some trips take more moves, and it found the small cases with a short computer program printed in an appendix ^[1].

One of its results is simple to picture. On a square board with sides of at least 3, a single blocking piece anywhere except a corner square pushes the longest rook trip up from two moves to three ^[1].

The comparison with path puzzles is our own, not the paper's. Every finished path acts as a wall for the others, so the shortest route between two equal numbers keeps getting longer as the grid fills, just as the 3s in the worked example had to travel all the way around.

How do these puzzles connect to Hamilton cycles?

Picture a version with a single pair, where every cell must be used. The path then has to pass through every cell of the grid exactly once. That is a Hamilton path, the open version of a Hamilton cycle, which returns to its start after touring every point once.

Routes of this kind are hard to find in general. A paper published on 21 June 2011 notes that for decades the best known way to decide whether a network has a Hamilton cycle took time of order 2 raised to the number of points ^[2]. It adds that a randomised method later brought this down to about 1.657 raised to the number of points, times a smaller factor ^[2].

For a solver at the grid, the lesson is practical. Trying every route by brute force soon gets out of hand, so the forcing patterns above, not blind trial, are the way through a large puzzle.

What mistakes should you avoid?

• Taking the shortest route by habit. The obvious straight line between two numbers can be wrong, as path 3 showed.
• Forgetting that numbers are walls. A path can never pass through a number from a different pair.
• Ignoring stranded cells. Before you commit to a move, check that no empty cell is left with fewer than two usable neighbours.
• Drawing loops and spurs. A path is one line with two ends. It never branches and never enters the same cell twice, though it may fold back beside itself.
• Stopping before the last cell. In this version, an empty cell left over means a path must be rerouted.

How do you find the next move when nothing looks forced?

• Scan every empty cell and count its usable neighbours. Any cell with exactly two is a fresh corner.
• Look at the border again. Settled edge cells can decide cells further in.
• Pick the path end with the fewest choices and test each choice for stranded cells.
• If two neighbouring paths could swap a stretch of cells, look for a corner or edge cell that only one of them can reach.

Can you solve this practice puzzle?

Here is a six by six grid with five pairs. Join each pair and use every cell.

A hint: begin with the three empty corners, and you will find that path 1 takes the long way round.

Answer: we checked by computer that this is the only solution. Path 1 is the longest, at twelve cells, and path 5 simply runs along the top edge.

Path 2 fills the bottom left corner square of four cells, curling from the 2 in row 5 through the corner and up to the 2 in row 4. Here, too, the path runs beside itself: row 5, column 2 touches three cells of path 2, but its route neighbours are only row 5, column 3 before it and row 6, column 2 after it.

Enjoy following lines through a tangle? In this riddle, cords cross and wind between switches and lanterns, and you trace one route from end to end.