9
$\begingroup$

It is well-known (and has been asked here earlier) how many knights can fit on a chessboard without any knights attacking any others. But what if each knight can attack at most one other?

Idea from "The Mathematical Knight" by Noam Elkies and Richard Stanley.

$\endgroup$
  • $\begingroup$ This has the same answer as the previous question... $\endgroup$ – Xandawesome Jun 28 '15 at 23:28
11
$\begingroup$

The maximum possible is number of knights is:

32

This can be achieved by:

Putting a knight on every white square (thanks to Timtech for the graphic).

There's also other nontrivial configurations, like:

A knight on every edge or corner square (28), plus the four very center squares.

This is optimal because of existence of a construction with the following properties:

Partition the chessboard into 16 sets of 4 squares, with each set forming a a loop of four connected by knight moves.

One instance of this construction is:

Splitting the 4x4 square into four sets as follows

1342
4213
3124
2431

Then, split the chessboard into four 4*4 quadrants each with a copy of this pattern.

This construction proves optimality because:

Each set of 4 can only have 2 knights, since if there are 3, one knight must be attacking two knights. So, this gives a maximum of 2*16=32.

$\endgroup$
  • $\begingroup$ Nice graphic (spoiler): mathworld.wolfram.com/images/eps-gif/KnightsMax_700.gif $\endgroup$ – Timtech Nov 18 '14 at 12:11
  • $\begingroup$ Hiding all the content in this answer does not make a reader's experience better. I now have the choice to read the entirety of the spoiler block or nothing, as opposed to without the spoiler blocks, when I had the choice to read...the entire answer or nothing. Hiding only the most essential pieces of information (in this case, the number of squares) lets me know what your answer says, without actually knowing what it is. I can follow your reasoning while still ultimately working out the answer for myself. $\endgroup$ – Josh Caswell Nov 18 '14 at 19:13
  • $\begingroup$ @JoshCaswell Is that better? I tried to split everything into individually-spoilered steps. $\endgroup$ – xnor Nov 18 '14 at 22:03
  • $\begingroup$ Thanks for taking my comment into consideration; I think you could still un-spoiler more of each sentence without giving anything away, but I see what you're shooting for, and it is clear what each box is going to contain. $\endgroup$ – Josh Caswell Nov 19 '14 at 6:41
  • $\begingroup$ @JoshCaswell Unfortunately, spoilers can't be nested. I'd rather not take anything out of spoiler box to avoid someone reading an earlier box getting (mildly) spoiled on a later part. $\endgroup$ – xnor Nov 19 '14 at 6:47

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.