Problem of the Month (July 2006)

In the chess literature, the problem of placing the minimum number of pieces to attack every square of the chessboard is well known. This month we consider a natural extension, placing pieces on a board so that each square is attacked an equal number of times. That is, what is the minimum number of white chess pieces that can be placed on an n×n chessboard so that each vacant square is attacked exactly k times? What if we want to attack every square exactly k times? (We allow any number of pieces, in any location, so pawns can be on the first or last rank.)

Can you find solutions with few pieces for n=3? What about larger square boards? What about rectangular boards? Are the answers different if you are allowed to use both black and white pieces?

ANSWERS

Let V(n,k) be the fewest number of chess pieces needed so that each vacant square of an n×n chessboard is attacked exactly k times.

Joe DeVincentis showed that:

V(n,1)≤n   V(n,2)≤n, V(n,3)≤2n-2   V(n,4)≤2n   V(n,5)≤3n-2   V(n,6)≤4n-4   V(n,7)≤4n-4   and   V(n,8)≤4n-4.

These bounds seem to be sharp for k=2, k=7, and k=8.

Here are the best known solutions.

2×2, Vacant Squares Attacked k Times
1
2
3

 

3×3, Vacant Squares Attacked k Times
1
2
3
4
5
6
7
8

 

4×4, Vacant Squares Attacked k Times
1

  		2

  		3

(Joe DeVincentis) 		4

 
5

(Heinrich Hemme) 		6

  		7

  		8

 
9

(James Wilson) 		10

  		11

  		12

 
 

5×5, Vacant Squares Attacked k Times
1

  		2

  		3

(Dirk Riehm) 		4

 
5
6
7
8
9

  		10

  		11

(James Wilson) 		12

 
13

(James Wilson) 		14

  		15

  		16

 
 

6×6, Vacant Squares Attacked k Times
1

  		2

  		3

(Joe DeVincentis) 		4

 
5
6
7
8
9

  		10

  		11

(James Wilson) 		12

 
13

(James Wilson) 		14

  		15

  		16

 
 

7×7, Vacant Squares Attacked k Times
1

(Joe DeVincentis) 		2

  		3

(Joe DeVincentis) 		4

 
5
6
7
8
9

(James Wilson) 		10

(James Wilson) 		11

  		12

(James Wilson)
13

(James Wilson) 		14

  		15

  		16

 
 

Here are the best known results when every square must be attacked an equal number of times.

2×2, All Squares Attacked k Times
1

  		2

(James Wilson) 		3

 
 

3×3, All Squares Attacked k Times
1

  		2

(Joe DeVincentis) 		3

 
 

4×4, All Squares Attacked k Times
1

  		2

(Bernd Rennhak) 		3

(Bernd Rennhak) 		4

 
 

5×5, All Squares Attacked k Times
1

(Bernd Rennhak) 		2

  		3

(Bernd Rennhak) 		4

(Bernd Rennhak)
 

6×6, All Squares Attacked k Times
1

  		2

(Bernd Rennhak) 		3

(Bernd Rennhak) 		3

(Bernd Rennhak)
 

7×7, All Squares Attacked k Times
1

  		2

  		3

(Bernd Rennhak)
 

8×8, All Squares Attacked k Times
1

(Bernd Rennhak)
 

9×9, All Squares Attacked k Times
1

(Bernd Rennhak)
 

Bernd Rennhak considered the problem of attacking every square on an 4×n chessboard exactly k times.

4×n, All Squares Attacked k Times
1234

(Bernd Rennhak)
(Bernd Rennhak)
(Bernd Rennhak)
(Bernd Rennhak)

(Bernd Rennhak)
(Bernd Rennhak)
(Bernd Rennhak)
(Bernd Rennhak)

(Bernd Rennhak)
(Bernd Rennhak)

(Bernd Rennhak)
 

(Bernd Rennhak)
 

Bernd Rennhak also considered the problem of attacking every square on triangular chessboards exactly k times.

Triangles, All Squares Attacked k Times
123

 
 

 
 

(Bernd Rennhak)
(Bernd Rennhak)

(Bernd Rennhak)
(Bernd Rennhak)
(Bernd Rennhak)

(Bernd Rennhak)
(Bernd Rennhak)
(Bernd Rennhak)

(Bernd Rennhak)
(Bernd Rennhak)
 

Bernd Rennhak has these pages with more information.

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 3/13/07.