Independence problem: one rook and maximum number of knights on the chessboard $8 \times 8$

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.

Solution 1:

$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:

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.

  And 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.
  

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:

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.

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

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:

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.

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

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.

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

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

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

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

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

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:

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

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

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.

Solution 2:

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:

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:

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.

Solution 3:

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  .  .  .  .  .  .