Note: There are errors here, see revised article for corrected analysis.

How about non-extendable paths on toroidal boards?

It’s easy enough to modify my script to do that. Change two lines. Boom. What’s not so easy is running the modified script, because it takes a lot longer. Analyzing a 3x3 torus takes about 40 seconds, versus 0.2 seconds for the ordinary 3x3 board. 4x4? Takes more than two hours. Granted, that’s on my computer, which is not the fastest in the world, and it’s a Python script, and Python is not especially fast. Still. A while.

For 3x3 the minimum is 8 positions and there are 32 such paths.

For 4x4, 10 positions and 24 paths.

I also did the 2x2 torus (0.2 seconds), but I’m sure you can figure out what the one non-extendable path there is by hand. If you want 5x5, do it yourself. I don’t feel like waiting several days or weeks or whatever for it.

All right, all right. Here’s one non-extendable path on the 5x5 torus.

(One annoying thing is that an odd torus can’t be checkerboard-colored, even if my script attempted to do so with the 3x3 torus solutions above. This means color parity arguments don’t work.)

I claim that at 14 positions (13 moves), this path is the shortest possible length.

For terminal positions a knight’s move apart, one neighbor of each terminal coincides with the other terminal, and three other neighbors of one terminal coincide with neighbors of the other, so there are only 16-2-3 = 11 neighbor positions that have to be covered. Three of these neighbors form a cluster in which they connect only to each other by single moves, and the other eight likewise. So you need at least 11 (to cover the neighbors) + 1 (to link the two clusters) + 1 (to reach the end) = 13 moves.

For terminal positions at any other separation, only two neighbors of one terminal coincide with neighbors of the other, so there are 14 neighbor positions to cover. In each case all 14 are in a cluster connected by single moves, so there might be a path of 15 moves, but none shorter.

<– 2023-08-05_non-extendable-knights-paths-part-2 — 2023-08-08_nonextendable-knights-paths-part-4 –>