16
$\begingroup$

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

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

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

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Very nice work Rob and worthy of the tick! Thank you for finding the 16 knight solution. Also I suggest adding this to OEIS. $\endgroup$ – Dmitry Kamenetsky Mar 10 at 22:17
  • $\begingroup$ Rob check out the other solutions I found below. $\endgroup$ – Dmitry Kamenetsky Mar 11 at 6:49
17
$\begingroup$

Here is a solution with 15 knights:

enter image description here

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

I could not find a solution with 14 knights.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Wow amazing work! How did you do that? $\endgroup$ – Dmitry Kamenetsky Mar 10 at 12:04
  • 4
    $\begingroup$ I wrote a computer progam ... $\endgroup$ – daw Mar 10 at 12:18
  • 1
    $\begingroup$ Interesting that you found 15 knights, but not 14. In my experience 14 is much easier... $\endgroup$ – Dmitry Kamenetsky Mar 10 at 12:19
  • 2
    $\begingroup$ it would be great if you could share the idea behind your program, as it is not a trivial task. $\endgroup$ – Dmitry Kamenetsky Mar 10 at 18:01
  • $\begingroup$ Is the program on github, would you share it? $\endgroup$ – stevec Mar 12 at 11:11
9
$\begingroup$

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:

    1 from corner, first go

    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:

    1 from corner, second go

    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:

    1 from corner, third go

    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:

    2 from corner, first go

    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:

    3 from corner, first go

    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:

    3 from corner, second go

    3 from corner, third go

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

    3 from corner, fourth go

    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:

    3 from corner, fifth go

    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:

    3 from corner, sixth go

    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?

| improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ 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/… $\endgroup$ – Steve Mar 10 at 10:58
  • 4
    $\begingroup$ You seem to assume that all or zero fields on the border two tile away from the corner have to be filled. $\endgroup$ – daw Mar 10 at 11:28
  • 2
    $\begingroup$ @daw Yeah, I was assuming symmetry. Surprising that an asymmetric solution exists! $\endgroup$ – Rand al'Thor Mar 10 at 12:24
6
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ I don't think the e2 knight works. $\endgroup$ – Yonatan N Mar 10 at 20:32
  • 1
    $\begingroup$ @Yonatan The g2 knight wandered off. I've put him back where he belongs. $\endgroup$ – Daniel Mathias Mar 10 at 20:38
  • $\begingroup$ This looks great! Nice one! $\endgroup$ – Yonatan N Mar 10 at 20:39
0
$\begingroup$

I found 3 other solutions with 16 knights. Enjoy!

1.

enter image description here

2.

enter image description here

3.

enter image description here

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

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.