Knights in a Complete Sudoku Board

Question

In a complete Sudoku board, at most how many chess knights would it be possible to place on its cells with a 1 inside, so that each knight can walk in order (1, 2, 3, ..., 9) through cells numbered up to 9, no two of the knights overlapping in their trajectories?

Answer 1

The most knights that can walk a Sudoku board (to my knowledge) is

$\begin{array}{cc} {Knights} & {Moves} \\ {6} & {9} \\ {7} & {8} \\ {8} & {7} \\ {9} & {1} \\ \end{array}$

This image shows 6 knights making $9$ moves, and a 7th knight only makes it to $8$



My method was to first permute all the nine $1$ starting positions, 5907 without symmetry (as noted by @DanielMathias). Taking the $1$s seven at a time, I then placed $2$s at all possible knight moves obeying Sudoku rules. That left two $2$s with two rows and two columns unused, a further possible two perms without knight moves (but subject to Sudoku rules).

I then moved each of the seven knights on $2$ in all ways, again permuting the last two $3$s without knight rules. Ditto for the other moves as far as possible to $9$. Moving the knights in parallel filled as much of the grid as early as possible and reduced the search space enough to allow an exhaustive search for a 7-knight solution.

This image shows 8 knights trying $8$ moves, but the last 3 knights only make it to $7$



This used a similar technique, again an exhaustive search in a fairly short time.

In a comment @JaapScherphuis used parity to explain why the 9 knights can't move beyond the first placing:

The 9 knights all occupy a different row and column, and the sum of the row and column numbers is $90$ which has $0$ parity. If they all move to number $2$, the same would apply, $0$ parity. But a knight move is $(2 + 1)$ squares so each would reverse its parity. For an odd number of knights, their combined parity would reverse – which it can't.

I had also tried to work out solutions with pen and paper. The 4x4 Sudoku solution neatly has each knight follow a "circular" route, with two types of route. I had wondered if a similar scheme for 9x9 could be found, with different types of interweaving circular routes, but Jack's parity rule prevents that for a single knight, because after $9$ steps its parity is reversed and it cannot end up where it started, whereas on an even-sized board it can.

Another approach I tried by hand was based around the hope that I could devise a set of jigsaw-like pieces:



and other variations, and fit them together. But that did not come to anything, partly because in these examples the centre cell must always be a $1$ or a $9$.

Answer 2

Still trying various integer linear programming formulations. Along the way, I found that if you ignore the sudoku constraints, you can fit 9 knight paths. Not an answer, but I wanted to share the picture:

Answer 3

Here is a solution my program found.

As MathJax array:

Six complete paths, each in its own color:
$$\begin{array}{|ccc|ccc|ccc|} \hline \, \color{#800000}{1} & \color{#AAAAAA}{8} & \color{#000080}{7} & \color{#800000}{6} & \color{#AAAAAA}{5} & \color{#AAAAAA}{2} & \color{#000080}{3} & \color{#AAAAAA}{9} & \color{#AAAAAA}{4}\,\\ \,\color{#AAAAAA}{4} & \color{#800000}{5} & \color{#800000}{2} & \color{#AAAAAA}{1} & \color{#AAAAAA}{3} & \color{#000080}{9} & \color{#AAAAAA}{8} & \color{#008000}{7} & \color{#AAAAAA}{6}\,\\ \,\color{#800000}{3} & \color{#000080}{6} & \color{#AAAAAA}{9} & \color{#000080}{8} & \color{#800000}{7} & \color{#000080}{4} & \color{#008000}{1} & \color{#000080}{2} & \color{#008000}{5}\,\\ \hline \,\color{#AAAAAA}{9} & \color{#A000A0}{7} & \color{#800000}{4} & \color{#000080}{5} & \color{#008000}{2} & \color{#000080}{1} & \color{#008000}{6} & \color{#AAAAAA}{3} & \color{#008000}{8}\,\\ \,\color{#AAAAAA}{2} & \color{#AAAAAA}{3} & \color{#A000A0}{5} & \color{#AAAAAA}{7} & \color{#AAAAAA}{6} & \color{#800000}{8} & \color{#008000}{9} & \color{#008000}{4} & \color{#A0A000}{1}\,\\ \,\color{#A000A0}{6} & \color{#A000A0}{1} & \color{#A000A0}{8} & \color{#A0A000}{9} & \color{#00A0A0}{4} & \color{#008000}{3} & \color{#A0A000}{2} & \color{#A0A000}{5} & \color{#AAAAAA}{7}\,\\ \hline \,\color{#AAAAAA}{7} & \color{#A000A0}{4} & \color{#00A0A0}{1} & \color{#A000A0}{2} & \color{#800000}{9} & \color{#A0A000}{6} & \color{#00A0A0}{5} & \color{#00A0A0}{8} & \color{#A0A000}{3}\,\\ \,\color{#AAAAAA}{5} & \color{#A000A0}{9} & \color{#AAAAAA}{6} & \color{#00A0A0}{3} & \color{#A0A000}{8} & \color{#00A0A0}{7} & \color{#A0A000}{4} & \color{#AAAAAA}{1} & \color{#AAAAAA}{2}\,\\ \,\color{#AAAAAA}{8} & \color{#00A0A0}{2} & \color{#A000A0}{3} & \color{#AAAAAA}{4} & \color{#AAAAAA}{1} & \color{#AAAAAA}{5} & \color{#A0A000}{7} & \color{#00A0A0}{6} & \color{#00A0A0}{9}\,\\ \hline\end{array}$$

As text:

Six complete paths (a, b, c, d, e, f)

 1a 8  7d 6a 5  2  3d 9  4 
 4  5a 2a 1  3  9d 8  7c 6 
 3a 6d 9  8d 7a 4d 1c 2d 5c
 9  7f 4a 5d 2c 1d 6c 3  8c
 2  3  5f 7  6  8a 9c 4c 1e
 6f 1f 8f 9e 4b 3c 2e 5e 7 
 7  4f 1b 2f 9a 6e 5b 8b 3e
 5  9f 6  3b 8e 7b 4e 1  2 
 8  2b 3f 4  1i 5  7e 6b 9b

This is now a final result, as exhaustive searching has shown that no solution exists with seven complete paths.

See WeatherVane's answer for more detail.

Answer 4

Here, courtesy Freddy Barrera, is the puzzle solved for a smaller board: