9
$\begingroup$

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:

chessboard willed with knights, except with A6 to A1 empty, as well as B1 to G1 and B2 to G2 empty

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

$\endgroup$

2 Answers 2

8
$\begingroup$

This has been confirmed to be optimal.

13 moves:
Merging knights

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 N

Step 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 N

Step 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 N

Step 4:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . N N
. . . . . . N N
. . . N N N N N
N N N N N N N N

Step 5:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . N N
. . . . . N N N
. . N N N N N N
. . . . . . N N

Step 6:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . N N N N N N
. . . . N N N N

Step 7:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . N N
. . . . N N N N

Step 8:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . N N N N

Step 9:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . N N N
. . . . . . . .
. . . . . . . N

Step 10:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . N
. . . . . . . .
. . . . . . N N

Step 11:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . N
. . . . . . . .
. . . . . . . N

Step 12:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . N . .
. . . . . . . N

Step 13:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . N

$\endgroup$
4
  • $\begingroup$ Nice job. Is this using a computer program? $\endgroup$ Feb 6 at 18:04
  • $\begingroup$ @DmitryKamenetsky Not yet. $\endgroup$ Feb 6 at 18:46
  • 1
    $\begingroup$ @DmitryKamenetsky Exhaustive search confirms this to be optimal. $\endgroup$ Feb 6 at 21:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Feb 7 at 21:10
5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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". $\endgroup$
    – trolley813
    Feb 6 at 19:26
  • 1
    $\begingroup$ @trolley813 updated, thanks. $\endgroup$ Feb 6 at 19:38
  • 2
    $\begingroup$ Exhaustive search confirms these to be optimal. See edit for link to code. $\endgroup$ Feb 6 at 21:31

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.