Knights attacking exactly three knights

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

• I think we have too many variations on the "arrange pieces on a chessboard" theme now. Mar 10 '20 at 21:56
• @Brilliand this was the last one, I promise :P Mar 10 '20 at 22:18
• Maybe we should just make "Chess pieces attacking exactly N chess pieces" and have them all collected in one place? Mar 10 '20 at 23:20
• @DarrelHoffman that's a good idea. Feel free to start it. Mar 11 '20 at 1:17
• Done Mar 11 '20 at 2:02

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

• Very nice work Rob and worthy of the tick! Thank you for finding the 16 knight solution. Also I suggest adding this to OEIS. Mar 10 '20 at 22:17
• Rob check out the other solutions I found below. Mar 11 '20 at 6:49

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.

• Wow amazing work! How did you do that? Mar 10 '20 at 12:04
• I wrote a computer progam ...
– daw
Mar 10 '20 at 12:18
• Interesting that you found 15 knights, but not 14. In my experience 14 is much easier... Mar 10 '20 at 12:19
• it would be great if you could share the idea behind your program, as it is not a trivial task. Mar 10 '20 at 18:01
• Is the program on github, would you share it? Mar 12 '20 at 11:11

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.

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

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

• I think you went wrong in your first simplification - assuming that all knights are on a square of their own colour. See the "knights" part of my answer to a related problem puzzling.stackexchange.com/questions/94421/… Mar 10 '20 at 10:58
• You seem to assume that all or zero fields on the border two tile away from the corner have to be filled.
– daw
Mar 10 '20 at 11:28
• @daw Yeah, I was assuming symmetry. Surprising that an asymmetric solution exists! Mar 10 '20 at 12:24

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.

• I don't think the e2 knight works. Mar 10 '20 at 20:32
• @Yonatan The g2 knight wandered off. I've put him back where he belongs. Mar 10 '20 at 20:38
• This looks great! Nice one! Mar 10 '20 at 20:39

I found 3 other solutions with 16 knights. Enjoy!

1.

2.

3.

• It turns out that there are 52 possible solutions with 16 knights. Mar 11 '20 at 18:18
• Wow so many! Would love to see them. Mar 11 '20 at 21:25
• I have them in a text file but don't see any way to attach it. Mar 11 '20 at 21:38
• @RobPratt perhaps you can save it on something like pastebin and then send us the link to it. Mar 13 '20 at 0:00