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.

Improve this question
$\endgroup$
1
  • $\begingroup$ This has the same answer as the previous question... $\endgroup$
    – Xandawesome
    Jun 28, 2015 at 23:28

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Nice graphic (spoiler): mathworld.wolfram.com/images/eps-gif/KnightsMax_700.gif $\endgroup$
    – Timtech
    Nov 18, 2014 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$
    – jscs
    Nov 18, 2014 at 19:13
  • $\begingroup$ @JoshCaswell Is that better? I tried to split everything into individually-spoilered steps. $\endgroup$
    – xnor
    Nov 18, 2014 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$
    – jscs
    Nov 19, 2014 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, 2014 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.