# Merging knights

A standard 8x8 chess grid is filled with knights. Each turn you can issue a move in one of 8 directions available to a chess knight. This will move all the knights in that direction. If a knight would jump out of board then it stays in its location. Otherwise the knight will jump in the issued direction. If a knight lands on another knight then they merge into one. For example, issuing the move "2 up and 1 right" from the starting grid would give you the following grid:

Is it possible to merge all the knights into one? What is the least number of turns required for that?

This has been confirmed to be optimal.

13 moves:

Confirmed optimal via exhaustive search. Pastebin link to code

Search depth 12 returns in about 40 seconds with no solutions. Search depth 13 returns in about 5 minutes, finding 68 solutions with first move forced ESE to avoid primary symmetries. The first of these is shown here in generated output:

Step 1: . . . . . . N N . . N N N N N N . . N N N N N N . . N N N N N N . . N N N N N N . . N N N N N N . . N N N N N N N N N N N N N NStep 2: . . . . . . N N . . . . . . N N . . . . N N N N . . . . N N N N . . . . N N N N . . . . N N N N . . . . N N N N N N N N N N N NStep 3: . . . . . . . . . . . . . . . . . . . . . N N . . . . . . N N . . . . N N N N . . . . N N N N . . . . N N N N N N N N N N N N NStep 4: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . N N . . . . . . N N . . . N N N N N N N N N N N N NStep 5: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . N N . . . . . N N N . . N N N N N N . . . . . . N NStep 6: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . N N N N N N . . . . N N N NStep 7: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . N N . . . . N N N NStep 8: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . N N N NStep 9: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . N N N . . . . . . . . . . . . . . . NStep 10: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . N . . . . . . . . . . . . . . N NStep 11: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . N . . . . . . . . . . . . . . . NStep 12: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . N . . . . . . . . . NStep 13: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . N

• Nice job. Is this using a computer program? Feb 6, 2022 at 18:04
• @DmitryKamenetsky Not yet. Feb 6, 2022 at 18:46
• @DmitryKamenetsky Exhaustive search confirms this to be optimal. Feb 6, 2022 at 21:30
• I confirmed optimality via integer linear programming. The minimum number of knights after each move is $46, 32, 18, 12, 9, 7, 5, 4, 4, 3, 2, 2, 1$, respectively. Feb 7, 2022 at 21:10

I was originally preparing what I thought was a better solution than I actually have, when another answer was posted. But I'll post it anyway, because I had already reached the answer, and because the sequence is different.

I also have it in

13 moves

Move 1: 2 up and 1 right
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline N & N & N & N & N & N & N & N \\ \hline N & N & N & N & N & N & N & N \\ \hline \quad & N & N & N & N & N & N & N \\ \hline \quad & N & N & N & N & N & N & N \\ \hline \quad & N & N & N & N & N & N & N \\ \hline \quad & N & N & N & N & N & N & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \end{array}$$

Move 2: 2 up and 1 left
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline N & N & N & N & N & N & N & N \\ \hline N & N & N & N & N & N & N & N \\ \hline N & N & N & N & N & N & N & \quad \\ \hline N & N & N & N & N & N & N & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & N & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & N & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \end{array}$$

Move 3: 2 up and 1 right
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline N & N & N & N & N & N & N & N \\ \hline N & N & N & N & N & N & N & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \end{array}$$

Move 4: 1 up and 2 right
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline N & N & N & N & N & N & N & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & N & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \end{array}$$

Move 5: 1 down and 2 right
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline \quad & \quad & \quad & \quad & \quad & \quad & N & N \\ \hline \quad & \quad & N & N & N & N & N & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \end{array}$$

Move 6: 1 up and 2 right
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline \quad & \quad & \quad & \quad & N & N & N & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & N & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \end{array}$$

Move 7: 1 down and 2 right
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline \quad & \quad & \quad & \quad & \quad & \quad & N & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & N & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \end{array}$$

Move 8: 2 down and 1 right
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \end{array}$$

Move 9: 1 up and 2 left
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline \quad & \quad & \quad & \quad & \quad & N & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & N & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & N & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \end{array}$$

Move 10: 1 up and 2 right
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline \quad & \quad & \quad & \quad & \quad & N & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \end{array}$$

Move 11: 1 up and 2 left
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline \quad & \quad & \quad & \quad & \quad & N & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \end{array}$$

Move 12: 2 down and 1 right
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & N & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \end{array}$$

Move 13: 2 up and 1 right
$$\begin{array}{|c|c|c|c|c|c|c|c|} \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & N \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \quad & \quad & \quad & \quad & \quad & \quad & \quad & \quad \\ \hline \end{array}$$

It was generated by a recursive C program in under a second. I reduced the search space:

For any given board, there are eight possible outcomes.
I explored only those outcomes with the least, or equal least, survivors.
For example if the eight moves left 4, 6, 6, 8, 4, 8, 5, 9 survivors,
I explored only the two with 4 survivors.

Later, I also explored those outcomes equal to or 1 greater than the least.
So for the above example I explored the ones with 4, 4, and 5 survivors.
It took a while longer, but no better solutions were found.

• One minor remark: In chess notation, the abbreviation "K" is used for kings, not knights. Knights are abbreviated either "N" or (more old-fastioned and mostly obsolete) "Kt". Feb 6, 2022 at 19:26
• @trolley813 updated, thanks. Feb 6, 2022 at 19:38
• Exhaustive search confirms these to be optimal. See edit for link to code. Feb 6, 2022 at 21:31