5
$\begingroup$

A chess grid is filled with knights and rooks as shown in the following diagram.

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 or onto a rook then it stays in its current location. Otherwise the knight will jump in the issued direction. If a knight lands on another knight then they merge into one. Starting from the following position, is it possible to merge all the knights into one? What is the least number of turns required to do so? You may need to use a computer to solve this puzzle.

starting position of the chessboard filled with knights and rooks. The Knights occupy the four centre squares, and are also arranged in four lots of hollow three by three squares with each square flush with a board corner. Every other position is filled by a Rook.

$\endgroup$
3
  • $\begingroup$ So, to clarify, rooks never move, right? $\endgroup$
    – justhalf
    Feb 9 at 9:12
  • $\begingroup$ correct rooks never move $\endgroup$ Feb 9 at 10:28
  • 1
    $\begingroup$ I read the title as "merging knights and blocking rocks," and proceeded to be surprised by the distinct lack of rocks. $\endgroup$
    – Avi
    Feb 9 at 23:50

2 Answers 2

3
$\begingroup$

I have found a solution

One knight remains after 16 moves

enter image description here

I don't know if this is optimal, the search was not exhaustive.

Found 2 solutions with a hand-made C program.

$\endgroup$
15
  • 1
    $\begingroup$ I can't see anything in the rules that stops you merging the last two knights from your final position. E.g. (probably far from optimal, just the first way I spotted "by eye") 1D2L, 2U1L, 2U1R, 1D2L, 2U1L, 1U2R $\endgroup$
    – fljx
    Feb 9 at 21:28
  • $\begingroup$ @fljx well spotted but the last one should be 1D2L from c7 to a6. Six more moves is a lot deeper than my non-exhaustive search. I'm fiddling with its efficency and trying to shrink the search space. The previous version wasn't so demanding. $\endgroup$ Feb 9 at 21:42
  • $\begingroup$ 1U2R (a6-c7) works (rook on e8 blocks the c7 knight) $\endgroup$
    – fljx
    Feb 9 at 22:03
  • 1
    $\begingroup$ I have an estimate of about 4 hours for a fully exhaustive search. Currently running search from position after 2 moves. $\endgroup$ Feb 10 at 0:44
  • 3
    $\begingroup$ I confirmed optimality via integer linear programming. The minimum number of knights after each move is 26, 19, 14, 11, 9, 6, 5, 4, 4, 3, 3, 3, 2, 2, 2, 1, respectively. $\endgroup$
    – RobPratt
    Feb 10 at 14:03
4
$\begingroup$

By request, here's the integer linear programming formulation I used. Let $C$ be the set of $36$ cells that are not blocked by rooks. Let $t$ be the target number of steps, and let $S=\{0,\dots,t\}$ be the set of steps. Let $D=\{(d_i,d_j)\in \mathbb{Z}^2:|d_i d_j| = 2\}$ be the set of eight directions. Let binary decision variable $x_{i,j,s}$ indicate whether cell $(i,j)$ is occupied by a knight at step $s$. Let binary decision variable $y_{d_i,d_j,s}$ indicate whether direction $(d_i,d_j)$ is chosen at step $s$. The problem is to minimize $\sum_{(i,j)\in C} x_{i,j,t}$ subject to \begin{align} \sum_{(d_i,d_j) \in D} y_{d_i,d_j,s} &= 1 &&\text{for $s \in S \setminus \{0\}$} \tag1\\ x_{i,j,0} &= 1 && \text{for $(i,j) \in C$} \tag2\\ \sum_{\substack{(d_i,d_j) \in D:\\ (i+d_i,j+d_j) \notin C}} y_{d_i,d_j,s} + x_{i,j,s-1} - 1 &\le x_{i,j,s} && \text{for $(i,j) \in C, s \in S \setminus \{0\}$} \tag3\\ y_{d_i,d_j,s} + x_{i-d_i,j-d_j,s-1} - 1 &\le x_{i,j,s} && \text{for $(i,j) \in C, s \in S \setminus \{0\}, (d_i,d_j) \in D: (i-d_i,j-d_j) \in C$} \tag4\\ \end{align} Constraint $(1)$ selects exactly one direction at each step. Constraint $(2)$ fixes the initial configuration of knights at step $0$. Constraint $(3)$ enforces the rule that a knight that cannot move in the chosen direction stays in place. That is, $$(y_{d_i,d_j,s} \land x_{i,j,s-1}) \implies x_{i,j,s}.$$ Constraint $(4)$ enforces the rule that a knight that can move in the chosen direction does so. That is, $$(y_{d_i,d_j,s} \land x_{i-d_i,j-d_j,s-1}) \implies x_{i,j,s}.$$

I solved the problem for each $t$ from $1$ to $16$ to obtain the optimal values $$26, 19, 14, 11, 9, 6, 5, 4, 4, 3, 3, 3, 2, 2, 2, 1.$$

So $t=16$ is the minimum number of steps needed to yield one knight.

$\endgroup$
2
  • 1
    $\begingroup$ My present solution goes in two stages. First it exhaustively finds S survivors after M moves, removes duplicate solutions (but not symmetries), and then exhaustively continues to find 1 survivor after N moves. Strangely, when I set S=2 and M=13 from your result it doesn't find a solution for N, but for N+1. Similarly when I set S=3 and M=10. But when I set S=4 and M=11, it does. So aiming for the minimum survivors possible at each move, does not solve it in the minimum moves. $\endgroup$ Feb 13 at 7:35
  • 2
    $\begingroup$ Yes, the behavior you describe is a known pitfall of greedy algorithms. I did not mention it in my answer, but after solving step $s$, I also added a constraint that the number of knights after $s$ steps must be at least (but not necessarily equal to) the minimum just determined. This optional constraint helps prune the search space without losing optimality. $\endgroup$
    – RobPratt
    Feb 13 at 15:08

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.