Knights attacking exactly three knights

Question

Can you place 14 black and 14 white knights on a standard 8x8 chess board, such that each knight attacks exactly 3 opponent knights? Bonus question: can you do it with 15 black and 15 white knights?

Good luck!

Here is a related question: Queens attacking exactly four queens

Answer 1

There are solutions for number of knights on each side equal to 4, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16. For example, here's one for 16:

. . 2 1 2 1 . .
. 2 . 2 1 . 1 .
. 1 2 1 2 1 2 .
1 . . . . . . 2
2 . . . . . . 1
. 2 1 2 1 2 1 .
. 1 . 1 2 . 2 .
. . 1 2 1 2 . .

I used integer linear programming, with a binary decision variable $x_{i,j,k}$ to indicate if cell $(i,j)$ contains a knight of color $k$. For each cell $(i,j)$, let $N_{i,j}$ be the set of neighboring cells (one knight's move away). You can define this set compactly as $$N_{i,j}=\{i'\in\{1,\dots,8\}, j'\in \{1,\dots,8\}:|i-i'|\cdot|j-j'|=2\}.$$ The constraints are: \begin{align} \sum_{i,j} x_{i,j,k} &= n &&\text{for all $k$}\\ \sum_k x_{i,j,k} &\le 1 &&\text{for all $i,j$}\\ 3 x_{i,j,k} \le \sum_{(i',j')\in N_{i,j}} x_{i',j',k'} &\le 3 + (|N_{i,j}|-3)(1 - x_{i,j,k}) &&\text{for all $i,j,k,k' \not= k$} \end{align} The first constraint forces exactly $n$ knights of each color. The second constraint forces at most one knight per cell. The third constraint forces exactly 3 opponent neighbors if $x_{i,j,k}=1$.

Answer 2

Here is a solution with 15 knights:

Note the slight non-symmetry in columns a-d, while e-h are symmetric.

I could not find a solution with 14 knights.

Answer 3

First observation: the colour of the knights corresponds to the colour of the squares - the black knights must be all on one colour and the white knights all on the other colour, since a knight's move always changes colour. So in my pictures I'm just going to put all knights in red, and aim for overall 4-fold rotational symmetry with 28 knights each attacking 3 others.

Second observation: we can't use the corners of the board, since those attack only 2 other squares.

1. Let's try using the edge squares just one away from the corner. Each of these attacks exactly 3 other squares, so we have:

   

   Now we have 8 knights in the outer ring of squares (edges of the board), 4 in the second ring, 4 in the third ring. The ones in the second ring are already attacking 3 enemy knights, so that tells us a bunch of squares that can't contain another knight. For each of the remaining outer-edge knights (two away from the corners), there's now only one place for the 3rd knight it attacks:

   

   Then for each of those newly placed knights (corner of each L-shaped formation), it's already attacking 1 knight and we can't put a knight in the corner, so there's only one way to place the remaining 2:

   

   But now we have 28 knights and the new edge ones (three away from the corners) are only attacking 2 other knights each. Contradiction!

So we cannot use either the corners or the edge squares one away from them.

2. Let's try using the edge squares two away from each corner. Given the restriction mentioned just above, there's only one way to place 3 knights attacked by each of these:

   

   But now we already have some knights (not on the outer ring of edge squares, or the second ring, but in the third ring) which attack five other knights. Contradiction!

So the only edge squares we can use are the two in the middle of each edge.

3. Each one of these edge squares (three away from the corners) attacks 4 other squares, of which 3 must be filled. Let's assume first that the squares diagonally two from each corner are filled:

   

   Each of those new knights attacks the following (allowed) squares: one of the remaining empty edge squares (outer ring); one square in the second ring; and two of the central squares. If the central squares are filled, then clearly we don't have enough space left to place all the remaining knights; so instead we get the second of the following figures:

   
   
   

   Now, considering each knight in the second ring, there's only one way to place the 2 remaining knights it attacks:

   

   Now there are only 4 knights still to be placed; but some of the edge knights are only attacking 1 knight! It's impossible to finish. Contradiction, so the squares diagonally two from each corner cannot be filled and we have:

   

   For each knight next to the corner (in the second ring), it's already attacking 2 knights and the 3rd one must be either in the outer ring (edge square) or in the third ring. Filling those squares in the third ring gives a contradiction with too many knights attacking each other, so we must fill the outer-ring ones:

   

   But now some of those outer-ring knights don't have enough squares available to attack 3 others! Contradiction again.

The problem seems impossible. Where have I gone wrong?

Answer 4

For the 14 v 14 solution:

Place 7 white knights on light squares and 7 black knights on dark squares such that each knight attacks three others. Then duplicate this pattern with white on dark an black on light.

lichess link

Answer 5

I found 3 other solutions with 16 knights. Enjoy!

1.

2.

3.