KNIGHT COVERING PROOFS

KNIGHT COVERINGS
OPTIMALITY PROOFS

Solutions to the knight covering problem for boards up to 10x10 have been known since 1896. These can be seen on the webpage kn3.htm
Here are some very clear and simple proofs that these coverings are optimal. That is, coverings with fewer knights are not possible.

3x3 Optimality

       We will start with a general result that will be useful in proving the optimality for several board sizes. We will show that it takes a minimum of 4 knights to cover any 3x3 square, regardless of its position on the board.
       Figure 1 shows a 3x3 square centered in a 7x7 area. Any knight outside the 7x7 area cannot attack any of the squares in the central area. Figure 2 shows the number of squares in the center area that are covered by a knight placed in any of the 49 squares. For example, a knight placed at (1,4) would attack the 2 squares (3,3) and (3,5).
       Any one knight can cover up to 3 squares in the center 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. Therefore at least 4 knights are needed to cover any 3x3 area.
       It follows immediately that 4 knights are needed to cover a 3x3 board.




X	X	X
X	X	X
X	X	X

Figure 2
0	1	1	2	1	1	0
1	2	2	2	2	2	1
1	2	3	3	3	2	1
2	2	3	1	3	2	2
1	2	3	3	3	2	1
1	2	2	2	2	2	1
0	1	1	2	1	1	0

4x4 Optimality

Four knights are needed to cover a 4x4 board. This follows immediately from the result above. Four knights are needed to cover the 3x3 area indicated.

Figure 3
X	X	X
X	X	X
X	X	X

5x5 Optimality

       Five knights are needed to cover a 5x5 board. Suppose this were not true, and that there exists a covering with only 4 knights. Then these knights would need to cover an average of 6¼ squares each.
       Figure 4 shows the number of squares covered by a knight in each of the 25 positions on the board. There are only 5 squares where knights would cover 6 or more squares. Suppose that the 9-square were not used. Then at least 3 of the 7-squares would have to be used in order to cover 25 squares altogether. However, using 3 of the 7-squares would cover some squares twice, so knights on three 7-squares would cover only 15 squares altogether. Therefore, the 9-square at the center of the board must be used.
       It is also necessary to use at least one 7-square, because 9+5+5+5 < 25. So the 9-square and at least one 7-square must be used. By symmetry we can choose any of the four 7-squares. Figure 5 shows the squares that are covered by the knights on the 7-square and 9-square.
       The remaining 2 knights must cover the 9 remaining uncovered squares. Figure 6 shows the number of these 9 squares that would be covered by a knight on each of the squares on the board. To cover 9 squares the 2 knights would have to be on 2 of the 3 squares that cover 5 squares. However, any 2 knights at these positions cover 2 squares in common, so that 2 knights in these positions can cover only 8 of the 9 remaining squares. Thus a 5x5 board cannot be covered by 4 knights. A minimum of 5 knights are required.

Figure 4
3	4	5	4	3
4	5	7	5	4
5	7	9	7	5
4	5	7	5	4
3	4	5	4	3

Figure 5
*	*	*	*
*			*	*
	7	9
*			*	*
*	*	*	*

Figure 6
1	1	1	2	3
1	3	5	1	0
2	0	0	5	3
1	3	5	1	0
1	1	1	2	3

6x6 Optimality

Eight knights are required to cover a 6x6 board. Consider the 6x6 board in Figure 7 with lettered squares on the top and bottom rows. At least 2 knights are needed to cover the 3 squares on the top row labeled A. None of these knights can cover any of the squares on the top row labeled B, so another 2 knights are needed to cover the three B squares. None of these 4 or more knights can cover any of the squares on the bottom row. So an additional 4 knights are needed to cover the bottom row. This makes a minimum of 8 knights.

Figure 7
A	B	A	B	A	B




B	A	B	A	B	A

7x7 Optimality

Ten knights are required to cover a 7x7 board. Consider the 10 squares marked A in Figure 8. No knight can cover more than one of these squares, so a minimum of 10 knights are required.

Figure 8
A	A		A
	A		A



A		A
A		A	A

8x8 Optimality

Twelve knights are required to cover an 8x8 board. Consider the 12 squares marked A in Figure 9. No knight can cover more than one of these squares, so a minimum of 12 knights are required.

Figure 9
A	A	A	A
	A	A




	A	A
A	A	A	A

9x9 Optimality

Fourteen knights are required to cover a 9x9 board. Consider the 14 lettered squares in Figure 10. A minimum of 3 knights are needed to cover the A squares, 4 knights are needed to cover the B squares, 4 knights are needed for the C squares, and 3 knights are required for the D squares. Since no knight can cover squares in two different lettered sections a minimum of 14 knights are required.

Figure 10
A	A		B	B	B
	A		B	B	B
			B	B	B



C	C	C
C	C	C		D
C	C	C		D	D

10x10 Optimality

Sixteen knights are required to cover a 10x10 board. Consider the 36 lettered squares in Figure 11. 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.

Figure 11
A	A	A	B	B	B
A	A	A	B	B	B
A	A	A	B	B	B




C	C	C	D	D	D
C	C	C	D	D	D
C	C	C	D	D	D

Quick Links

HOME

SITE MAP