8x8 board

On the Fediverse, @sam_hartburn@mathstodon.xyz asks :

What’s the shortest sequence of knight’s moves you can make on a chessboard such that the path is blocked at both ends (i.e. from either end of the sequence there are no squares you can move to that you haven’t already landed on)?

and provides a candidate path, one with 10 positions linked by 9 moves from the starting square to the ending one.

To make things clearer, we want a path consisting of an ordered list of positions separated by knight’s moves. Each position is to be visited only once. The start and end, or terminal, squares each have up to eight neighbor squares one knight’s move away, and all such neighbors must appear in the path.

Some people in the replies starting working up arguments for why 10 positions must be the minimum. They might be complete and correct. I, of course, just started working up a Python script to do a relatively brain dead exhaustive search. Pick a starting square, add linked positions to one end until you can’t, then add to the other end until you can’t. Or until you have a path that’s already as long as the shortest non-extendable path already found. Count them all up after eliminating duplicates up to rotation, reflection, and direction reversal.

Not completely brain dead. There are only 10 starting points worth considering, for instance, because of symmetry.

Another observation: You’re adding at both ends. So starting, for instance, at a corner square and generating all such paths gives you all paths that include a corner square anywhere in the path. Then if you start on a non corner square, there’s no need to consider corner squares when adding positions. More generally, all squares that have already been considered as starting squares (and their symmetry partners) need not be considered when generating paths with later starting squares. This gives a big speedup.

A smarter approach, probably, would be to take all possible combinations of start and end positions, add their neighbors, observe that you can get from some of these positions to some of the others via a single move while other pairs require 2, 3, or more moves, and then search for the shortest path through all the positions starting at one terminal and ending at the other. But efficient algorithms to do that seem to be hard.

So do I have a bug free script that generates all non-extendable paths? Maybe! Or maybe not. I don’t see any problems, but there could be some. I find 74 paths with 10 positions, and none with fewer. @Elmusfire@mathstodon.xyz posted their complete set of solutions, and it’s larger than my allegedly complete set, but on close inspection they didn’t get rid of all the duplicates. Eliminating them might put us in agreement.

nxn boards

Of course it’s easy enough to have the script consider boards of other sizes. I checked square boards up through 12x12, determining the minimum number of positions in a non-extendable path and the number of such paths. @Elmusfire points out one of the 8x8 solutions fits within a 4x4 square, meaning that for any finite board of size 4x4 or larger, the minimum length non-extendable path is no longer than 10 positions. But for some boards, shorter paths exist. On a 4x4 board, for instance, there are 2 paths with 7 positions:

Two non-extendable paths with 7 positions on a 4x4 board. One goes (0,0), (1,2), (3,1), (1, 0), (0, 2), (2, 1), (3, 3). The other is (0, 0), (1,2), (2,0), (0,1), (1,3), (2,1), (3,3).

Two non-extendable paths with 7 positions on a 4x4 board

Likewise there are shorter paths on the 5x5, 6x6, and 7x7 boards. But I was surprised to discover there are shorter paths on the 9x9 board too! Since consecutive squares in a knight’s path alternate colors, a path from one corner (which has only two neighbors, so is a favorable place for a terminal) to an adjacent corner requires an odd number of positions for odd-order squares and an even number for even-order squares. On the 8x8 board no 8-position path is long enough to link two adjacent corners and cover all four neighbors (and you could try for a 9-position path linking diagonally opposite corners, but there isn’t one), so it makes sense 10 positions is the minimum, but on the 9x9 there are two 9-position paths that do link adjacent corners and include the four neighbors.

For 11x11 and 12x12 there are no shorter paths. All the 10-position paths are close to one corner, not making use of the opposite edges, so both boards have the same set of solutions, and presumably so do all boards larger than 11x11, square or not. The 8x8 and 10x10 solutions are just the 11x11 solutions plus 5 and 3 additional solutions, respectively, that go from corner to corner.

A summary of my findings:

Board size Min positions # solutions
1x1 1 1
2x2 1 1
3x3 1 1
4x4 7 2
5x5 7 3
6x6 8 5
7x7 9 6
8x8 10 74
9x9 9 2
10x10 10 72
11x11 10 69
12x12 10 69

∞x∞ boards

@Elmusfire also raises the question: What is the shortest non-extendable path on an infinite board? One that extends infinitely in all directions, with no edges?

You’d have to have a path that hits a total of at least 18 squares: The start and end squares, and the eight neighbors of each — except that with some positions of the terminal squares, some of these 18 squares coincide.

You probably want the terminal squares to be opposite colors; otherwise all the neighbor squares are the same color, and a path linking them has to hit equally many non-neighbor squares of opposite colors in between.

Suppose, for instance, the terminal squares are adjacent. Then the squares that have to be visited are these:

Adjacent terminal squares (marked with hollow circles) and their neighbors (solid circles of the same color). The squares shown should be understood to be part of an infinite board with no edges.

Adjacent terminal squares (marked with hollow circles) and their neighbors (solid circles of the same color). The squares shown should be understood to be part of an infinite board with no edges.

Two sets of six neighbors are linked by single moves into a pair of cycles:

Two cycles consisting of six neighbors linked by single moves

Two cycles consisting of six neighbors linked by single moves

Call these 1-neighbors. The four remaining neighbors need two or more moves to link to each other or to anything else (except the terminals). Call these 2-neighbors. Then we could, for instance, make a chain from a terminal square to six 1-neighbors via single moves and then two 2-neighbors via double moves:

Terminal square to 1-neighbor with single move (magenta), five more 1-neighbors with single moves (green), and two 2-neighbors with double moves (orange).

Terminal square to 1-neighbor with single move (magenta), five more 1-neighbors with single moves (green), and two 2-neighbors with double moves (orange).

Or we could maybe go from a terminal to three 1-neighbors, then go to a 2-neighbor, and from there to three 1-neighbors of the other 6-cycle, ending up with another 2-neighbor:

Terminal square to 1-neighbor with single move (magenta), two more 1-neighbors with single moves (green), a 2-neighbor with double move (orange), another 1-neighbor with double move (red), two more 1-neighbors with single moves (dark blue), and a 2-neighbor with double move (yellow).

Terminal square to 1-neighbor with single move (magenta), two more 1-neighbors with single moves (green), a 2-neighbor with double move (orange), another 1-neighbor with double move (red), two more 1-neighbors with single moves (dark blue), and a 2-neighbor with double move (yellow).

Either way there are one terminal, six 1-neighbors, and two 2-neighbors, but in the first case we used 10 moves and in the second we used 11.

The first of these could be duplicated for the other 9 squares using 10 more links. Then if there were a way to go from the non-terminal end of one path to that of the other in 1 move, we’d have a 21-move (22-position) non-extendable path. But these non-terminal ends are 2-neighbors so they need at least 2 moves to connect to each other. In fact, since the terminal squares are opposite color, we need an odd number of moves to connect them, so the shortest non-extendable path using this strategy would have to be at least 23 moves (24 positions). One such path is shown:

24-position non-extendable path with adjacent terminals, consisting of two congruent 10-move paths (magenta and green) linked by a triple move (red)

24-position non-extendable path with adjacent terminals, consisting of two congruent 10-move paths (magenta and green) linked by a triple move (red)

Others exist. This doesn’t quite rise to the level of a proof that 24 positions is the minimum for adjacent terminal squares, but maybe it points the way to a proof.

What about other terminal positions? Here they are separated by a knight’s move; there are only 2-cycles of 1-neighbors, making for more double moves needed, but each terminal square coincides with a neighbor of the other terminal so there are fewer squares that have to be visited.

Terminal squares a knight’s move apart, their neighbors, and single move links between neighbors

Terminal squares a knight’s move apart, their neighbors, and single move links between neighbors

These considerations balance each other so that 24-position solutions are possible, but a 22-position solution appears not to be.

Edit: The following path is erroneous! See revised article for corrected path.

24-position non-extendable path with terminals separated by knight’s move, consisting of two congruent 10-move paths (magenta and green) linked by a triple move (red)

24-position non-extendable path with terminals separated by knight’s move, consisting of two congruent 10-move paths (magenta and green) linked by a triple move (red)

More distant separations of the terminal squares seem to require longer paths. I’m confident 24 positions is the minimum.

Solutions

Here are the solutions my script found for boards from 4x4 to 11x11. The order of appearance is the order they were found, which is not a very useful order — sorry!

4x4:
[[0, 0], [1, 2], [3, 1], [1, 0], [0, 2], [2, 1], [3, 3]]
[[0, 0], [1, 2], [2, 0], [0, 1], [1, 3], [2, 1], [3, 3]]

5x5:
[[0, 0], [1, 2], [2, 4], [3, 2], [1, 3], [2, 1], [4, 0]]
[[0, 0], [1, 2], [2, 0], [3, 2], [1, 3], [2, 1], [4, 0]]
[[0, 0], [1, 2], [3, 3], [2, 1], [1, 3], [3, 2], [4, 0]]

6x6:
[[0, 0], [1, 2], [2, 4], [3, 2], [4, 0], [2, 1], [1, 3], [0, 5]]
[[0, 0], [1, 2], [3, 3], [2, 1], [1, 3], [3, 2], [2, 4], [0, 5]]
[[0, 0], [1, 2], [3, 3], [2, 1], [4, 2], [2, 3], [3, 5], [5, 4]]
[[0, 0], [1, 2], [3, 1], [1, 0], [0, 2], [2, 1], [4, 2], [5, 0]]
[[0, 0], [1, 2], [3, 1], [2, 3], [0, 2], [2, 1], [4, 2], [5, 0]]

7x7:
[[0, 0], [1, 2], [0, 4], [2, 5], [1, 3], [2, 1], [0, 2], [1, 4], [0, 6]]
[[0, 0], [1, 2], [0, 4], [2, 5], [1, 3], [2, 1], [3, 3], [1, 4], [0, 6]]
[[0, 0], [1, 2], [0, 4], [2, 5], [3, 3], [2, 1], [0, 2], [1, 4], [0, 6]]
[[0, 0], [1, 2], [2, 4], [4, 5], [3, 3], [2, 1], [4, 2], [5, 4], [6, 6]]
[[0, 0], [1, 2], [3, 1], [5, 2], [4, 0], [2, 1], [3, 3], [4, 1], [6, 0]]
[[0, 0], [1, 2], [2, 0], [4, 1], [3, 3], [2, 1], [4, 0], [5, 2], [6, 0]]

8x8:
Same as 11x11 but adding:
[[0, 0], [1, 2], [3, 3], [2, 1], [0, 2], [1, 4], [2, 6], [3, 4], [1, 5], [0, 7]]
[[0, 0], [1, 2], [3, 3], [2, 1], [0, 2], [2, 3], [1, 5], [3, 4], [2, 6], [0, 7]]
[[0, 0], [1, 2], [3, 3], [2, 1], [1, 3], [3, 2], [5, 1], [4, 3], [6, 2], [7, 0]]
[[0, 0], [1, 2], [3, 3], [2, 1], [4, 0], [3, 2], [5, 1], [4, 3], [6, 2], [7, 0]]
[[0, 0], [1, 2], [3, 3], [2, 1], [4, 2], [2, 3], [1, 5], [3, 4], [2, 6], [0, 7]]

9x9:
[[0, 0], [1, 2], [3, 3], [2, 1], [4, 2], [6, 1], [5, 3], [7, 2], [8, 0]]
[[0, 0], [1, 2], [3, 3], [2, 1], [4, 0], [6, 1], [5, 3], [7, 2], [8, 0]]

10x10:
Same as 11x11 but adding:
[[0, 0], [1, 2], [3, 3], [2, 1], [1, 3], [0, 5], [1, 7], [3, 6], [2, 8], [0, 9]]
[[0, 0], [1, 2], [3, 3], [2, 1], [1, 3], [2, 5], [1, 7], [3, 6], [2, 8], [0, 9]]
[[0, 0], [1, 2], [3, 3], [2, 1], [4, 0], [5, 2], [7, 1], [6, 3], [8, 2], [9, 0]]

11x11 (and all larger finite boards):
[[0, 0], [1, 2], [3, 3], [2, 1], [0, 2], [1, 4], [2, 2], [4, 3], [3, 1], [1, 0]]
[[0, 0], [1, 2], [3, 3], [2, 1], [0, 2], [2, 3], [3, 1], [4, 3], [2, 2], [1, 0]]
[[0, 0], [1, 2], [3, 3], [2, 1], [1, 3], [3, 4], [2, 2], [4, 1], [2, 0], [0, 1]]
[[0, 0], [1, 2], [3, 3], [2, 1], [1, 3], [3, 2], [2, 0], [4, 1], [2, 2], [0, 1]]
[[0, 1], [2, 2], [4, 1], [3, 3], [1, 2], [0, 0], [2, 1], [1, 3], [3, 2], [2, 0]]
[[0, 0], [1, 2], [3, 1], [2, 3], [0, 2], [2, 1], [1, 3], [0, 1], [2, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [2, 3], [0, 2], [2, 1], [1, 3], [3, 4], [2, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [2, 3], [0, 2], [2, 1], [3, 3], [1, 4], [2, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [2, 3], [0, 2], [2, 1], [3, 3], [4, 1], [2, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [2, 3], [0, 2], [2, 1], [4, 2], [3, 0], [2, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [2, 3], [0, 2], [2, 1], [4, 2], [3, 4], [2, 2], [1, 0]]
[[0, 1], [2, 2], [4, 1], [5, 3], [3, 2], [1, 3], [2, 1], [0, 0], [1, 2], [2, 0]]
[[0, 0], [1, 2], [3, 1], [2, 3], [4, 2], [2, 1], [0, 2], [1, 4], [2, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [4, 3], [2, 2], [0, 1], [1, 3], [2, 1], [0, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [4, 3], [2, 2], [1, 4], [3, 3], [2, 1], [0, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [4, 3], [2, 2], [3, 4], [1, 3], [2, 1], [0, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [4, 3], [2, 2], [3, 4], [4, 2], [2, 1], [0, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [4, 3], [2, 2], [4, 1], [3, 3], [2, 1], [0, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [4, 3], [2, 2], [3, 0], [4, 2], [2, 1], [0, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [5, 2], [4, 0], [2, 1], [0, 2], [1, 4], [2, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [5, 2], [3, 3], [2, 1], [0, 2], [1, 4], [2, 2], [1, 0]]
[[0, 0], [1, 2], [3, 1], [5, 0], [4, 2], [2, 1], [0, 2], [1, 4], [2, 2], [1, 0]]
[[0, 0], [1, 2], [2, 0], [3, 2], [1, 3], [2, 1], [0, 2], [1, 4], [2, 2], [0, 1]]
[[0, 0], [1, 2], [2, 0], [3, 2], [1, 3], [2, 1], [0, 2], [1, 0], [2, 2], [0, 1]]
[[0, 0], [1, 2], [2, 0], [3, 2], [1, 3], [2, 1], [3, 3], [1, 4], [2, 2], [0, 1]]
[[0, 0], [1, 2], [2, 0], [3, 2], [1, 3], [2, 1], [3, 3], [4, 1], [2, 2], [0, 1]]
[[0, 0], [1, 2], [2, 0], [3, 2], [1, 3], [2, 1], [4, 2], [3, 0], [2, 2], [0, 1]]
[[0, 0], [1, 2], [2, 0], [3, 2], [1, 3], [2, 1], [4, 2], [3, 4], [2, 2], [0, 1]]
[[0, 0], [1, 2], [2, 0], [3, 2], [4, 0], [2, 1], [1, 3], [3, 4], [2, 2], [0, 1]]
[[0, 0], [1, 2], [2, 0], [4, 1], [2, 2], [1, 0], [0, 2], [2, 1], [1, 3], [0, 1]]
[[0, 0], [1, 2], [2, 0], [4, 1], [2, 2], [1, 4], [0, 2], [2, 1], [1, 3], [0, 1]]
[[0, 0], [1, 2], [2, 0], [4, 1], [2, 2], [1, 4], [3, 3], [2, 1], [1, 3], [0, 1]]
[[0, 0], [1, 2], [2, 0], [4, 1], [2, 2], [3, 4], [4, 2], [2, 1], [1, 3], [0, 1]]
[[0, 0], [1, 2], [2, 0], [4, 1], [2, 2], [3, 0], [4, 2], [2, 1], [1, 3], [0, 1]]
[[0, 0], [1, 2], [2, 0], [4, 1], [3, 3], [2, 1], [1, 3], [3, 4], [2, 2], [0, 1]]
[[0, 1], [2, 2], [4, 1], [5, 3], [3, 2], [1, 3], [2, 1], [3, 3], [1, 2], [2, 0]]
[[0, 1], [2, 2], [4, 1], [5, 3], [3, 2], [1, 3], [2, 5], [0, 4], [1, 2], [2, 0]]
[[0, 1], [2, 2], [4, 1], [5, 3], [3, 2], [1, 3], [2, 5], [3, 3], [1, 2], [2, 0]]
[[0, 1], [2, 2], [4, 1], [5, 3], [3, 2], [1, 3], [0, 5], [2, 4], [1, 2], [2, 0]]
[[0, 1], [2, 2], [4, 1], [5, 3], [3, 4], [1, 3], [3, 2], [2, 4], [1, 2], [2, 0]]
[[0, 1], [2, 2], [4, 1], [3, 3], [1, 2], [2, 4], [0, 5], [1, 3], [3, 2], [2, 0]]
[[0, 1], [2, 2], [4, 1], [3, 3], [1, 2], [0, 4], [2, 5], [1, 3], [3, 2], [2, 0]]
[[0, 1], [2, 2], [4, 1], [3, 3], [2, 1], [1, 3], [3, 2], [2, 4], [1, 2], [2, 0]]
[[0, 1], [2, 2], [4, 1], [3, 3], [2, 5], [1, 3], [3, 2], [2, 4], [1, 2], [2, 0]]
[[0, 1], [2, 2], [3, 4], [1, 3], [3, 2], [5, 3], [4, 1], [3, 3], [1, 2], [2, 0]]
[[0, 1], [2, 2], [3, 4], [1, 3], [3, 2], [2, 4], [1, 2], [3, 3], [4, 1], [2, 0]]
[[0, 1], [1, 3], [3, 2], [2, 4], [1, 2], [3, 1], [1, 0], [2, 2], [4, 1], [2, 0]]
[[0, 1], [1, 3], [3, 2], [5, 3], [4, 1], [2, 2], [1, 0], [3, 1], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 2], [1, 1], [3, 0], [2, 2], [4, 1], [3, 3], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 2], [1, 1], [0, 3], [2, 2], [4, 1], [3, 3], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 2], [5, 1], [3, 0], [2, 2], [4, 1], [3, 3], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 2], [5, 1], [4, 3], [2, 2], [4, 1], [3, 3], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 2], [5, 3], [4, 1], [2, 2], [4, 3], [3, 1], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 2], [5, 3], [4, 1], [2, 2], [4, 3], [2, 4], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 2], [5, 3], [4, 1], [2, 2], [1, 4], [3, 3], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 2], [5, 3], [4, 1], [2, 2], [0, 3], [2, 4], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 2], [5, 3], [3, 4], [2, 2], [4, 1], [3, 3], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 2], [2, 4], [0, 3], [2, 2], [4, 1], [3, 3], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 2], [2, 4], [1, 2], [3, 1], [4, 3], [2, 2], [4, 1], [2, 0]]
[[0, 1], [1, 3], [3, 2], [2, 4], [1, 2], [3, 3], [1, 4], [2, 2], [4, 1], [2, 0]]
[[0, 1], [1, 3], [3, 2], [2, 4], [4, 3], [2, 2], [4, 1], [3, 3], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 4], [2, 2], [4, 1], [5, 3], [3, 2], [2, 4], [1, 2], [2, 0]]
[[0, 1], [1, 3], [3, 4], [2, 2], [4, 1], [3, 3], [1, 2], [2, 4], [3, 2], [2, 0]]
[[0, 3], [2, 4], [3, 2], [4, 4], [2, 3], [1, 5], [3, 4], [2, 2], [3, 0], [1, 1]]
[[0, 3], [1, 5], [2, 3], [4, 4], [3, 2], [2, 4], [4, 3], [2, 2], [3, 0], [1, 1]]
[[0, 3], [2, 2], [3, 0], [5, 1], [3, 2], [2, 4], [3, 6], [1, 5], [2, 3], [1, 1]]
[[0, 3], [2, 2], [3, 0], [4, 2], [2, 3], [1, 5], [3, 6], [2, 4], [3, 2], [1, 1]]
[[0, 3], [2, 4], [3, 2], [5, 1], [3, 0], [2, 2], [3, 4], [1, 5], [2, 3], [1, 1]]
[[0, 3], [1, 5], [2, 3], [4, 2], [3, 0], [2, 2], [4, 3], [2, 4], [3, 2], [1, 1]]

(Only first 7 rows and columns shown, the rest are empty.)