5
$\begingroup$

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

Good luck!

$\endgroup$
6
$\begingroup$

A possible way to cover the board with indicating the positions of the knights with "X" is:

enter image description here The conclusion is that it is possible to cover the board with 16 knights.

Next I will prove that with 15 knights it is not possible.

This is a 3x3 area/board inside of a 7x7 board. If a knight is placed on any of the squares of the middle part, the number how many squares are covered by it inside the middle part is written on its square. Any single knight can cover up to 3 squares in this 3x3 area. However, 3 knights cannot cover all 9 of the central squares because a knight in any of the 8 positions that cover 3 squares cannot cover the center square. The conclusion is that at least 4 knights are needed to cover any 3x3 area/board.

enter image description here

Lastly, consider this arrangement.

enter image description here

This is already a 10x10 board. A minimum of 4 knights are needed to cover each of the four 3x3 lettered areas. Since a knight cannot cover squares in two different lettered areas a total of at least 16 knights are required. In case of a 9x9 board there would be at least one knight that could cover one or more squares in two different lettered areas.

The conclusion:

It has been shown that it is possible to cover the 10x10 board with 16 knights. It also has been shown that at least 16 knights are required to cover the board, therefore it is the minimum number.

$\endgroup$
  • $\begingroup$ Beautiful work and a very nice explanation! You get full marks. Now can you prove the minimum for the 9x9 board? $\endgroup$ – Dmitry Kamenetsky Oct 15 at 10:50
  • $\begingroup$ Thanks.. Yes :) (I am sure someone else can, too) $\endgroup$ – balazs.com Oct 15 at 11:22
9
$\begingroup$

Here is a solution using

16

knights.

   . . . . . . . . . .
   . . . . . . x x . .
   . x x . . . x x . .
   . x x . . . . . . .
   . . . . . . . . . .
   . . . . . . . . . .
   . . . . . . . x x .
   . . x x . . . x x .
   . . x x . . . . . .
   . . . . . . . . . .

I believe this is minimal, but I do not yet have a proof.

The obvious lower bound is 12, as 11 knights can cover at most 88 squares, so there is at least $100-88-11=1$ square uncovered and empty.

This lower bound can be improved slightly if you take into account that a knight covering a corner can cover at most 6 squares. Suppose you use 12 knights. Four of the knights cover 6 squares (including one corner each), and the other 8 knights cover at most 8 squares, and that gives a total of at most $4*6+8*8+12=100$ squares that are covered or non-empty. However, there is no slack at all. For a solution with 12 knights to be possible, every square must be covered exactly once, no knight attacks another, and every knight covers 6 or 8 squares. When you try to place the knights to cover the squares near a corner of the board, it is soon obvious that you will have squares that are covered multiple times.

So at least 13 knights are necessary. There is unfortunately still a gap between this lower bound and what I believe to be the actual minimum.

I also tried to prove it by looking at this pattern:

x x . . . . . . . x
. x . . . . . . x x
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
x x . . . . . . x .
x . . . . . . . x x

Each of the twelve marked squares must be covered or contain a knight. However, no two of them can be covered/filled by a single knight (i.e. no two marked squares are one or two knight moves apart), so at least 12 knights are necessary. I have not yet been able to find a similar pattern with more marked squares.

$\endgroup$

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.