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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Nice job. Is this using a computer program? $\endgroup$
    – Dmitry Kamenetsky
    Feb 6, 2022 at 18:04
  • $\begingroup$ @DmitryKamenetsky Not yet. $\endgroup$
    – Daniel Mathias
    Feb 6, 2022 at 18:46
  • 1
    $\begingroup$ @DmitryKamenetsky Exhaustive search confirms this to be optimal. $\endgroup$
    – Daniel Mathias
    Feb 6, 2022 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, 2022 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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