10
$\begingroup$

On the chessboard $8 \times 8$ we can to place one rook and several knights. Find the maximum number of knights, which can be placed on a chessboard along with one rook so that none of the pieces attack each other.

My work. If a rook is placed in a square a8, then we can place the $25$ knights in all the white squares that rook doesn’t attack. I do not know how to prove that $25$ is the maximum number of knights.

$\endgroup$
  • 2
    $\begingroup$ On any rectangle which allows a knight's tour (closed not implied), the best is to choose the colour with the most squares (odd) or half the squares (even). Else you have two adjacent squares on the tour. But in other cases you can do better eg a $1\times n$ rectangle can be filled (apart from one square blocked by not attacking the rook). A $2 \times 5$ rectangle can have six squares filled, and a $2 \times 6$ rectangle can have $8$ (a scheme with blocks of four filled/blank works for strips of width two and shows you can do better other than for lengths divisible by $4$). $\endgroup$ – Mark Bennet Jun 10 at 21:21
6
+50
$\begingroup$

$25$ is the maximum possible and can be proven by case distinction.

First, notice that by a symmetry argument, we can reduce the number of placements for rook to $10$. Here are the possible placements for rook:

enter image description here

Now, there are few observations to make and few facts to be mentioned:

  • Let $K(n)$ be the maximum number of non-attacking knights that can be placed to $n\times n$ board. Then (source), $$K(n) = \begin{cases} \frac{n^2}{2}, & \text{if $n$ is even} \\[2ex] \frac{n^2+1}{2}, & \text{if $n$ is odd} \end{cases}$$

  • When we divide a board into $m$ rectangular boards with $K_i$ being the maximum number of non-attacking knights that can be placed to $i^{th}$ small board, we have $$K \le \sum_{i = 1}^m K_m$$ where $K$ is the maximum number of non-attacking knights that can be placed into non-divided board.

  • We might have different upper bounds for different board divisions. But in the end, we are trying to find the least upper bound.

  • When we have a $4\times n$ board with $n \ge 2$, maximum number of non-attacking knights that can be placed $K_4(n) = 2n$. For even $n$'s, this is really easy to prove by dividing the board into $2\times4$ small boards. Then we already know $K_4(2) = 4$ (my previous answer). For odd $n$'s, first we should observe $K_4(3) = 6$ (can be seen by trial and error). Then for $K_4(5)$, we are just adding a $2\times4$ board piece to $3\times4$ board. Here, you can use induction to obtain the result.

  • When we have a $1 \times n$ board, obviously, maximum number of non-attacking knights that can be placed is $n$. But we will try to avoid divisions where we have this case. Instead, we will try the next one.

  • When we have have a case as in the below where we can't place knights to red line, we can consider left side and right side of the line as a single $2 \times k$ board piece. This is because when we have a $2\times k$ board, whenever we place a knight to left $1\times k$ part, it threatens $1$ or $2$ squares in right $1\times k$ part. Notice that this is the same for the below case.

    enter image description hereAnd in order to find maximum number of non-attacking knights that can be placed, we can divide the board (green lines divides it) as in the figure and see that for each $4$ squares between the green lines, we can place $2$ knights.

  • When we have $3 \times 5$ board, we can place at most $8$ knights. This is also worth mentioning because we will see this case a lot. In order to prove, we can divide it into $3 \times 3$ where maximum is $5$, and $2 \times 3$ where maximum is $4$. So our upper bound is $9$. But, there is only two ways of placing $5$ knights to $3 \times 3$ board (shown below). In both cases, you can see that we can't place more than $3$ knights to $2 \times 3$ board. Therefore, $9$ is not achievable. Note that this will be our main proof idea from here onward.
    enter image description here

Now, we can look at the cases. I will write the maximum number of knights to each division and red notches will indicate where knights can threaten the rook (therefore we can't place knights):

Case 1: Rook in a1. This is an easy case since it leaves us with $7 \times 7$ board where we can't place knights to two of white squares. but on that $7 \times 7$ board, there are $25$ black squares. So we have $K_{a1} \le K(7) = \frac{7^2+1}{2} = 25$ by the first fact and indeed we can place $25$ knights as you suggested.

Case 2: Rook in b1. We can divide the board as in the following:

enter image description here

Here, we have $26$ as upper bound. However, this is still not bad because in order to achieve $26$, all the divisions must have maximum possible of knights. Therefore, whenever we prove we can't achieve maximum for a division, upper bound becocmes $25$.

Now, for blue part of the board, placement of $8$ knights is unique (shown below). And when we make that placement, $3$ squares of $3 \times 5$ board is threatened (shown by black notches). And dividing it into a $3 \times 3$ and a $2 \times 3$ board, if we use all $3$ unthreatened squares of $2 \times 3$, we can't place $5$ knights to $3 \times 3$ board. Therefore, we can't place $8$ knights to blue part and $3 \times 5$ board. Therefore, $26$ is not achievable in this case.

enter image description here

Case 3: Rook in b2. We can divide the board as in the following:

enter image description here

Here, we have $K_{b2} \le 25 = 13+6+4+2$.

Case 4: Rook in c1. We can divide the board as in the following:

enter image description here

Here, again we have $26$ as an upper bound. But if we focus left side of the board, we can see that if we place $2$ knights to $2 \times 2$ board, we can't place $6$ knights to $2 \times 5$ board (shown below). Therefore, $26$ is not achievable in this case.

enter image description here

Case 5: Rook in c2. We can divide the board as in the following:

enter image description here

Here, we have $26$ as an upper bound. But green part has a unique placement for $6$ knights (shown below). After that placement, we can observe that for $2 \times 5$ board, placement of $5$ knights is determined. After that, we should notice we can't place $8$ knights to $3 \times 5$ board. Therefore, $26$ is not achievable.

enter image description here

Case 6: Rook in c3. We can divide the board as the following:

enter image description here

Then, we have $K_{c3} \le 25 = 13+5+5+2$.

Case 7: Rook in d1. We can divide the board as the following:

enter image description here

Then, we have $K_{d1} \le 25 = 14+6+5$.

Case 8: Rook in d2. We can divide the board as the following:

enter image description here

Here, again we have $26$ as an upper bound. But it is easy to see that if we place $4$ knights to blue part, we can't place maximum of $2$ knights to $2 \times 1$ board. Therefore, $26$ is not achievable in this case.

Case 9: Rook in d3. We can divide the board as the following:

enter image description here

Then, we have $K_{d3} \le 25 = 10+8+4+3$.

Case 10: Rook in d4. We can divide the board as the following:

enter image description here

Then, we have $K_{d4} \le 25 = 8+6+6+5$.

Therefore, the maximum possible number is $25$.


Unfortunately, this is a very long solution and in some of $10$ cases, we found upper bound to be $26$ and forced to prove $26$ was not possible (maybe there are some divisions of board where $25$ is upper bound for these bad cases). I couldn't see a way to show $25$ is the maximum possible without a case distinction of rook placements. If there is an easier way, I am also glad to see that.

$\endgroup$
  • 1
    $\begingroup$ +1 but i wish you had put the $26$ knights solution first. that, to me, is the bigger news than the impossibility of $27$. :D $\endgroup$ – antkam Jun 14 at 19:02
  • 1
    $\begingroup$ really? i havent read your solution in detail yet. now i need to find the other $26$ knight solutions! :D $\endgroup$ – antkam Jun 14 at 19:12
  • 1
    $\begingroup$ oh no... sorry but your solution (at least the one now posted at the top) doesn't work. the rook is being attacked by 2 knights. (now that i think about it, i think this was posted before and then deleted by another person.) does any other of your $26$ knights solution work? $\endgroup$ – antkam Jun 14 at 19:53
  • $\begingroup$ @antkam Yes you were right. Answer turned out to be $25$, unfortunately. I focused on knights too much that I forgot knights could also threaten the rook. That was a really good point, thank you very much. $\endgroup$ – ArsenBerk Jun 14 at 21:56
  • 1
    $\begingroup$ Thank you very much! $\endgroup$ – Witold Jun 19 at 20:44
3
$\begingroup$

I am actually posting this to give you an idea since I don't think this answer is completed.


Below is the chess board with your rook placing. Now, let us divide the rest of the board into $4$ small boards as below:

enter image description here

Now, we can see that for $3 \times 3$ part, maximal placement is with $5$ knights, which we can verify even by trying all the cases (but placement is not unique). For $3 \times 4$ parts, maximal placement is with $6$ knights but this placement may not placing all $6$ knights to white or black squares. But we don't mind it for now. For $4 \times 4$ part, maximal placement is with $8$ knights. I will prove this here since the proof idea will be useful for us later:

Suppose for a contradiction that we can place $9$ knights to $4 \times 4$ board. Then, let us divide the board into two as in the following:

enter image description here

Then, by pigeonhole principle, one of the $2 \times 4$ squares must have $5$ knights. But again even with trying all the cases, we can see that we can't place $5$ knights in $2 \times 4$ board with the condition given, therefore $8$ is the maximum number of knights for $4 \times 4$ board.

Now, we can place maximum of $5$ knights to $3 \times 3$ board, $6$ knights to $3 \times 4$ boards and $8$ knight to $4 \times 4$ board, which gives $5+2\cdot6+8 = 25$ and supposing $26$ will give us a similar result to $4 \times 4$ case (We can suppose for a contradiction and prove $26$ knights is not possible).


Now, this is not a complete answer because when we place the rook to somewhere else, let's say b2, we are left with a $6 \times 6$ board, two $1 \times 6$ boards and a $1 \times 1$ board. Here, for $1 \times 6$ boards, if we take them separately, we can place $6$ knights to them, which will prevent us from using the above argument. Still I am posting this since it may give some idea to you and others.

$\endgroup$
1
$\begingroup$

In each of the 10 cases of rook placement considered by @ArsenBerk, you can get a certificate of optimality via linear programming duality. After removing the squares attacked by the rook, introduce a decision variable $x_{i,j}$, bounded by 0 and 1, for each remaining square $(i,j)$. The interpretation is that $x_{i,j}=1$ if and only if square $(i,j)$ contains a knight. Now the linear programming problem is to maximize $\sum_{i,j} x_{i,j}$ subject to conflict constraints of the form $x_{i,j} + x_{i',j'} \le 1$, where squares $(i,j)$ and $(i',j')$ are a knight's move from each other. In each case, the optimal objective value is 25, and the optimal dual variables indicate a partition of the board into $s$ single squares and $p$ pairs of conflicting squares with $s+p=25$. Trivially, each square can contain at most one knight, and each pair can contain at most one knight, so this partition proves that at most 25 knights can be placed. This idea is very similar to @ArsenBerk's partitions into larger subsets of squares, but here the partition is derived automatically as a by-product of the LP solve, and the certificate does not rely on optimal results for smaller boards.

For example, here is one such partition into 25 regions (21 pairs and 4 singletons) when the rook is placed in square b1:


 1  . 22  2  3  4 23  5 
 6  .  1  4  7  5  3  8 
24  .  6  9  2  8 10 11 
12  . 13  7 14 11 15 16 
13  . 12 17  9 18 19 10 
 .  .  . 14 20 21 16 15 
25  . 20  . 17 19 18 21 
 .  R  .  .  .  .  .  . 
$\endgroup$
  • $\begingroup$ Thank you very much! $\endgroup$ – Witold Jun 29 at 21:28

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.