# Problem of the Month (February 2015)

This month we are interested in another chessboard problem. What are the positions on an m × n chessboard using the most chess pieces (no pawns) so that each piece attacks exactly k unoccupied squares? When "most" is replaced by "fewest", the problem is not very interesting unless k=1. What are the best solutions in that case?

Solutions were received from Joe DeVincentis, Claudio Baiocchi, Maurizio Morandi, George Sicherman, and Bryce Herdt.

Here are the largest known number of pieces possible each attacking k vacant squares on an n × n square:

n \ k012345678910 11121314151617181920212223242526272829303132
11
24321
39865
(GS)
33
(GS)
21
41614121087
(GS)
6
(GS)
43
(GS)
41
5252120
(JD)
1613
(GS)
12
(GS)
1087
(GS)
6
(GS)
6
(GS)
44 2 1
6363228
(GS)
22
(GS)
2018
(GS)
16
(GS)
14
(GS)
1212
(GS)
10
(GS)
8
(GS)
8745
(MM)
24 1
7494339
(MM)
32
(GS)
29
(JD)
25
(GS)
22
(GS)
20
(GS)
18
(GS)
14
(GS)
16
(GS)
12
(MM)
12
(GS)
12
(MM)
8
(GS)
8
(JD)
8
(GS)
6
(GS)
7
(MM)
2
(JD)
4 2 1
86456
(MM)
52
(JD)
44
(GS)
36
(BH)
32
(GS)
30
(GS)
26
(GS)
24
(GS)
20
(GS)
20
(GS)
18
(GS)
16
(GS)
14
(GS)
14
(GS)
12
(GS)
12
(GS)
9
(GS)
9
(GS)
11
(GS)
8
(GS)
7
(GS)
2
(JD)
5
(GS)
4 1
9817264
(GS)
52
(GS)
49
(GS)
40
(GS)
37
(GS)
32
(BH)
30
(GS)
24
(GS)
24
(GS)
24
(GS)
24
(GS)
20
(GS)
20
(GS)
16
(MM)
15
(GS)
14
(GS)
12
(MM)
12
(JD)
11
(GS)
12
(GS)
11
(GS)
8
(GS)
9
(GS)
4
(JD)
6
(GS)
421

Clearly any full grid has no moves. We will not illustrate these. There are too many ties to show all duplicates. Here are the largest known number of pieces for square chessboards:

2 × 2 Chessboards
1
2
3

3 × 3 Chessboards
1
2
3 (GS)
4
5 (GS)
6
8

4 × 4 Chessboards
1
2
3
4
5 (GS)
6 (GS)
7
8 (GS)
9
11

5 × 5 Chessboards
1
2 (JD)
3
4 (GS)
5
6
7
8 (GS)
9 (GS)
10 (GS)
11
12
14
16

6 × 6 Chessboards
1
2 (GS)
3 (GS)
4
5 (GS)
6 (GS)
7 (GS)
8
9 (GS)
10 (GS)
11 (GS)
12
13
14
15 (MM)
16
17
19

7 × 7 Chessboards
1
2 (MM)
3 (GS)
4 (JD)
5 (GS)
6 (GS)
7 (GS)
8 (GS)
9 (GS)
10 (GS)
11 (MM)
12 (GS)
13 (MM)
14 (GS)
15 (JD)
16 (GS)
17 (GS)
18 (MM)
19 (JD)
20
22
24

8 × 8 Chessboards
1 (MM)
2 (JD)
3 (GS)
4 (BH)
5 (GS)
6 (GS)
7 (GS)
8 (GS)
9 (GS)
10 (GS)
11 (GS)
12 (GS)
13 (GS)
14 (GS)
15 (GS)
16 (GS)
17 (GS)
18 (GS)
19 (GS)
20 (GS)
21 (GS)
22 (JD)
23
25
27

9 × 9 Chessboards
1
2 (GS)
3 (GS)
4 (GS)
5 (GS)
6 (GS)
7 (BH)
8 (GS)
9 (GS)
10 (GS)
11 (GS)
12 (GS)
13 (GS)
14 (GS)
15 (MM)
16 (GS)
17 (GS)
18 (MM)
19 (JD)
20 (GS)
21 (GS)
22 (JD)
23 (GS)
24 (GS)
25 (JD)
26 (GS)
28
30
32

Here are the largest number of pieces known for rectangular chessboards:

Largest Known Number of Pieces
Attacking Exactly 1 Vacant Square
23456789
2
3
4
5
6
7
8
(MM)
(GS)
(MM)
9
(MM)
(MM)
(MM)
(MM)

Largest Known Number of Pieces
Attacking Exactly 2 Vacant Squares
23456789
2
3
4
5
(GS)
(JD)
6
(GS)
(GS)
(GS)
7
(MM)
(GS)
(JD)
(MM)
(MM)
8
(MM)
(MM)
(JD)
(GS)
(GS)
(JD)
9
(MM)
(MM)
(JD)
(MM)
(JD)
(JD)
(GS)

Largest Known Number of Pieces
Attacking Exactly 3 Vacant Squares
23456789
2
3
(GS)
4
5
(GS)
6
(GS)
7
(GS)
(GS)
(GS)
(GS)
(MM)
(GS)
8
(GS)
(GS)
(GS)
(GS)
(MM)
(GS)
9
(GS)
(GS)
(GS)
(MM)
(MM)
(MM)
(JD)
(GS)

Largest Known Number of Pieces
Attacking Exactly 4 Vacant Squares
23456789
2 none
3
4
5
(MM)
(GS)
6
(GS)
(BH)
7
(GS)
(GS)
(GS)
(GS)
(JD)
8
(MM)
(GS)
(GS)
(GS)
(MM)
(BH)
9
(BH)
(GS)
(GS)
(GS)
(GS)
(GS)
(GS)

Largest Known Number of Pieces
Attacking Exactly 5 Vacant Squares
23456789
2 none
3
(GS)
4
(GS)
5
(GS)
6
(GS)
(GS)
(GS)
(GS)
7
(GS)
(GS)
(GS)
(GS)
(GS)
8
(GS)
(GS)
(GS)
(GS)
(GS)
(GS)
9
(GS)
(GS)
(GS)
(GS)
(GS)
(MM)
(GS)
(GS)

Largest Known Number of Pieces
Attacking Exactly 6 Vacant Squares
23456789
2 none
3 none
4
(GS)
(GS)
5
(GS)
6
(GS)
(MM)
(GS)
7
(GS)
(GS)
(GS)
(GS)
(GS)
8
(MM)
(GS)
(GS)
(GS)
(MM)
(MM)
(GS)
9
(MM)
(GS)
(GS)
(GS)
(MM)
(MM)
(MM)
(GS)

Largest Known Number of Pieces
Attacking Exactly 7 Vacant Squares
23456789
2 none
3 none none
4 none
(GS)
5
(GS)
6
(GS)
(GS)
7
(MM)
(GS)
(GS)
(GS)
8
(GS)
(GS)
(GS)
(GS)
(GS)
(GS)
9
(GS)
(GS)
(GS)
(GS)
(GS)
(GS)
(GS)
(BH)

Largest Known Number of Pieces
Attacking Exactly 8 Vacant Squares
23456789
2 none
3 none
4 none
(GS)
5 none
(GS)
(GS)
6
(GS)
7
(GS)
(GS)
(GS)
8
(GS)
(GS)
(GS)
(GS)
(GS)
9
(GS)
(GS)
(GS)
(GS)
(GS)
(GS)
(GS)

Largest Known Number of Pieces
Attacking Exactly 9 Vacant Squares
23456789
2 none
3 none none
4 none
5 none
(GS)
6 none
(GS)
(GS)
(GS)
7
(GS)
(GS)
(GS)
8
(GS)
(GS)
(GS)
(GS)
(GS)
9
(GS)
(GS)
(GS)
(GS)
(GS)
(GS)

George Sicherman asked what the asymptotic density is for positions with a fixed value of k. In other words, what region with the largest density ρ of pieces can be used to tile the infinite plane so that each piece attacks exactly k unoccupied squares? Here are the best known results:

k=1
 x x x x x x x x
ρ = 16/17
k=2
ρ = 7/8
(GS)
k=3
ρ = 7/9
(GS)
k=4
ρ = 3/4
(GS)
k=5
ρ = 9/14
(GS)
k=6
ρ = 4/7
(GS)
k=7
ρ = 8/15
(GS)
k=8
ρ = 1/2
k=9
ρ = 9/20
(GS)
k=10
ρ = 4/9
(GS)
k=11
ρ = 2/5
(GS)
k=12
ρ = 2/5
k=13
ρ = 10/27
(GS)
k=14
ρ = 1/3
k=15
ρ = 2/7
k=16
ρ = 1/3
(GS)
k=17
ρ = 8/25
(GS)
k=18
ρ = 2/7
(GS)
k=19
ρ = 4/15
(GS)
k=20
ρ = 2/7
k=21
ρ = 4/17
(GS)
k=22
ρ = 1/4
(GS)
k=23
ρ = 2/9
(GS)
k=24
ρ = 2/7
(GS)
k=25
ρ = 2/9
(GS)
k=26
ρ = 1/5
(GS)
k=27
ρ = 2/9
(GS)
k=28
ρ = 2/9
(GS)
k=29
ρ = 1/5
(GS)
k=30
ρ = 1/5
(GS)
k=31
ρ = 4/21
(GS)
k=32
ρ = 1/5
k=33
ρ = 2/11
(GS)
k=34
ρ = 4/21
(GS)
k=35
ρ = 10/63
(GS)
k=36
ρ = 1/6
(GS)

Here are the smallest known number of pieces for rectangular chessboards when k=1:

Smallest Known Number of Pieces
Attacking Exactly 1 Vacant Square
23456789
2
3
4
5
(MM)
(GS)
6
(GS)
(MM)
7
(MM)
(MM)
(MM)
(MM)
(MM)
8
(MM)
(MM)
(MM)
(MM)
(MM)
?
9
(GS)
(MM)
(MM)
(MM)
? ? ?

What is the smallest possible asymptotic density ρ of pieces so that each attacks k unoccupied squares? Here are the best known solutions.

k=0
ρ = 1/2
k=1
ρ = 1/3
k=2
ρ = 2/9
(BH)
k=3
kings horizontally
surrounded by
vacant squares
ρ = 0
(GS)
k=4
surrounded by
vacant squares
ρ = 0
k=5
surrounded by
vacant squares
ρ = 0
k=6
surrounded by
vacant squares
ρ = 0
k=7
surrounded by
vacant squares
ρ = 0
k=8
surrounded by
vacant squares
ρ = 0

Bryce Herdt claims the best solutions for n≥9 mimic the solution for n=2, diamonds of 4 bishops located roughly equal distances from each other so as to attack the required number of squares.

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