7
$\begingroup$

What is the minimum number of knights you need to place on a 9x9 chess board, such that every empty cell is attacked by at least one knight?

Here is a similar question for a 10x10 chess board: Knights covering a 10x10 chess board

Hint:

Even though the two puzzles are similar, their solutions are quite different. Furthermore, knowing the answer to one may prove that the answer to the other one is minimal.

Good luck!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
14
$\begingroup$

Here is my attempt at the solution. I don't have any mathematical proof that this is the minimum no. of knights, but the steps I followed suggest that.

In the figures below, the yellow cells denote the knight's location, and the corresponding numbers denote their covering cells.

I first divided the square into 4 identical squares of 4X4 each (grey cells are the axes of symmetry). Then I tried to fill up the outer corner of each of those boxes (placing 1-4th knight): enter image description hereNext, I want to fill-up the grey cells. For this, I first put the 5th knight to the 4th one's left. This covers the right half of the grey cells completely, and half of the top half grey cells:enter image description hereKeeping in mind the symmetry, I continue to do the same till the 8th knightenter image description here Now, I have to put at least 1 knight inside every small 4X4 square. Note that the centre spot is empty; and from the symmetry it is clear that it will be populated by all those 4 knights in each 4X4 grid. That leads the following (placing of 9-12th knight): enter image description here The rest is easily filled up by visual inspection, giving me the final result (placing of 13 & 14th knight): enter image description here Thus, the minimal solution requires 14 knights

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ "I first divided the square into 4 identical.etc." ..is this only an intuition? In this case your arrival at a correct arrangement is a lucky thing,since there seems to be no existing correlation between growing number of "n"(nxn board) and a rule how symmetricity of the arrangement changes.To be concrete, in other words: can you use this approach in the case of n=11,15 or 18 (where the numbers of inequivalent optimal solutions( because of the lack of rotational or reflectional symmetricity) is very high (100, 63, 2551 respectively (ref.:OEIS6075 and related stuff)? I might be wrong though.. $\endgroup$
    – balazs.com
    Oct 14, 2019 at 22:12
  • 3
    $\begingroup$ This is a very nice answer. You may have not proved it, but you have convinced me that this is the best we can do. $\endgroup$
    – Dmitry Kamenetsky
    Oct 14, 2019 at 23:26
  • 1
    $\begingroup$ I looked into the OEIS as you mentioned, and indeed the symmetry thing does not work well for the numbers you mentioned (11, 15, 18); but for most of the dimensions, there is somewhat a symmetry involved. So, I would say my intuition at symmetry is an educated guess rather than a complete lucky one @balazs.com $\endgroup$
    – SamRoy
    Oct 15, 2019 at 3:55
  • $\begingroup$ Maybe you can get mathematical proof by working on the minimum number of knights? One can strike at most 8 fields so absolute minimum is 8 knights (8x8=64). But to strike a corner you have only two possible places each, each 'wasting' four fields, so now 10 knights is absolute minimum. Now find some other logically necessary overlaps (mostly to strike the perimeter) to up the minimum beyond 13 (which would be an "odd" number indeed). $\endgroup$
    – user3445853
    Oct 15, 2019 at 12:56
  • $\begingroup$ Yes, that is the right approach. Actually I thought till the 10th knight. After that it felt like doing it on hand using the symmetry would be easier @user3445853 $\endgroup$
    – SamRoy
    Oct 15, 2019 at 14:12
10
$\begingroup$

I think the minimum number of knights is:

14

the positions:

enter image description here

Improve this answer
$\endgroup$

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.