17
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ When you say "overlapping", do you just mean that no each cell can only be visited by at most 1 night, or that moving between cells will "invalidate" cells that it passes over without stopping at? (i.e. does moving from "1" to "2" only remove those cells, or does it also remove 2 or 4 of the cells between them?) Pictures are often helpful to explain! $\endgroup$ – Chronocidal Apr 22 at 8:04
  • $\begingroup$ @Chronocidal: Each cell can only be visited by at most 1 knight. $\endgroup$ – Bernardo Recamán Santos Apr 22 at 14:17
10
$\begingroup$

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$

enter image description here

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$

enter image description here

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:

enter image description here

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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Yes, I found out very early that nine nights could not each make a single move. See my updated answer for inspired results. No major breakthrough. $\endgroup$ – Daniel Mathias Apr 26 at 12:39
  • $\begingroup$ @DanielMathias your algorithms are quicker than mine. As I was posting the last update I found one move more for 8 knights, putting it the same as for 7 knights, which I feel should be better, and you confirm that both of them can be. $\endgroup$ – Weather Vane Apr 26 at 12:42
  • 6
    $\begingroup$ There's a simple proof that 9 knights cannot make a move. The 9 knights start on the 1s, which all have distinct rows/columns. The sum of the coordinates of the 9 knights is therefore $2*(1+2+...+9)$ which is an even number. The same should be the case when the knights have all moved to the 2s. However, every knight's move changes the parity, so after the nine knights have made a move the sum of.their coordinates will be odd. $\endgroup$ – Jaap Scherphuis Apr 26 at 16:56
  • $\begingroup$ @JaapScherphuis that is neat. $\endgroup$ – Weather Vane Apr 26 at 16:59
  • $\begingroup$ @RobPratt my first post showing a solution for 6 knights was incorrect because although my knight moves were also following sudoko rules, I had neglected to check whether the remaining 27 unfilled $0$ cells could be completed to make a valid sudoku (they could not), and that was the original reason for deleting the answer. $\endgroup$ – Weather Vane Apr 26 at 18:00
5
$\begingroup$

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: enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ Any knight's tour (Hamiltonian path) would qualify with 9 paths. $\endgroup$ – Daniel Mathias Apr 26 at 19:06
  • $\begingroup$ Yes, that is true. $\endgroup$ – RobPratt Apr 26 at 19:17
5
+75
$\begingroup$

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.

| improve this answer | |
$\endgroup$
3
$\begingroup$

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

enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ As a matter of interest, are you able to see my deleted answer? $\endgroup$ – Weather Vane Apr 22 at 14:23
  • $\begingroup$ @WeatherVane: no, didn't see it. Pity! $\endgroup$ – Bernardo Recamán Santos Apr 22 at 14:29
  • 1
    $\begingroup$ I have enabled it, but am hoping to find a better answer. $\endgroup$ – Weather Vane Apr 22 at 14:29
  • $\begingroup$ @WeatherVane: Good job! Please don´t remove it! And carry on your search! $\endgroup$ – Bernardo Recamán Santos Apr 22 at 14:34
  • 4
    $\begingroup$ I would prefer to find a brain solution, still looking at that. $\endgroup$ – Weather Vane Apr 22 at 14:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.