Minimum Number of Knights
Redmond English
puzzle:
1 ) What is the minimum number of knights that may be placed on a chess
board such that every square is attacked ?
2 ) Prove it.
3 ) Give an example of such an arrangement.
After twiddling for about 20 minutes I came up with an arrangement
using 16 knights, but not being very good with this kind of puzzle
there are undoubtedly better (ie. less knights) solutions. Can
anybody come up with them ?
Red/.
James Aspnes
>While fooling around with a chess program, I thought of the following
>puzzle:
>
>1 ) What is the minimum number of knights that may be placed on a chess
> board such that every square is attacked ?
Fourteen.
>2 ) Prove it.
We can consider the knights attacking white squares and the knights
attacking black squares independently. Examining the 906,192 ways to
place six knights on the 32 black squares shows that no such placement
attacks every white square. Thus at least seven knights are needed on
white squares and seven on black.
>3 ) Give an example of such an arrangement.
-*-*-*-*
*-NNNN*-
-*-*-*-*
*NN-*NN-
-*-*-*-*
*NNNNNN-
-*-*-*-*
*-*-*-*-
We found 15 other solutions in the 47,855,699,958,816 possible ways to
place 14 knights.
A considerably nastier search shows that 12 is optimal if the
knights are assumed to control the squares they occupy. The only
optimal solutions in that version are the same as the one that was
recently posted.
David Applegate
James Aspnes
James Aspnes
1) Show that you need eight rooks to attack every square on a
chessboard.
2) Attack every square using five queens.
3) How many bishops do you need to attack or occupy every square?
4) How many bishops do you need to attack every square?
5) Can you attack every square using fewer than twelve kings?
(Note: as in the previous problem, pieces don't attack the square they
occupy.)
These problems are solvable (we've done it.) They're probably even
all solvable by hand (:-]).
David Applegate
James Aspnes
Rob Hutchings
> Some other natural problems, in increasing order of difficulty:
>
> 1) Show that you need eight rooks to attack every square on a
> chessboard.
With less than 8, at least one rank and at least one file must be vacant.
Their intersection is neither attacked nor occupied.
(I use this type of argument again in (3) and (4)
> 2) Attack every square using five queens.
Should be in an FAQ, but I don't have an answer to hand.
> 3) How many bishops do you need to attack or occupy every square?
> 4) How many bishops do you need to attack every square?
(3) is easier than the corresponding question with knights, because with
bishops white and black squares can be treated independently.
Lets do the white squares.
There is a 4*5 rectangle with corners at a4, d1, e8, h5, from which using the
same reasoning as in (1) at least 4 white-square bishops are needed.
For question (3) 4 bishops are enough, placed EG on b5, d5, e4, g4.
But for question (4) 4 bishops are not enough; they would each have to be on a
different diagonal d1-h5, b1-h7, a2-g8, a4-e8, and also between them cover the
diagonals f1-a6, h1-a8, h3-c8, so that two of these three diagonals would only
have one bishop on each. The squares occupied by these single bishops would not
be attacked. Five bishops, on f3, e4, d5, b5, d7, are enough.
1So the answers to (3) and (4) are 8 and 10.
> 5) Can you attack every square using fewer than twelve kings?
NO. Four kings are needed to attack the corners, and four more to attack
the squares occupied by the first four. However these are arranged, you find
that you need four more to finish the job.
>
> These problems are solvable (we've done it.) They're probably even
> all solvable by hand (:-]).
>
>
> David Applegate
> James Aspnes
RobH