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?
ANSWERS
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 \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32
|
|---|
| 1 | 1
|
|---|
| 2 | 4 | 3 | 2 | 1
|
|---|
| 3 | 9 | 8 | 6 | 5
(GS) | 3 | 3
(GS) | 2 | | 1
|
|---|
| 4 | 16 | 14 | 12 | 10 | 8 | 7
(GS) | 6
(GS) | 4 | 3
(GS) | 4 | | 1
|
|---|
| 5 | 25 | 21 | 20
(JD) | 16 | 13
(GS) | 12
(GS) | 10 | 8 | 7
(GS) | 6
(GS) | 6
(GS) | 4 | 4 | | 2 | | 1
|
|---|
| 6 | 36 | 32 | 28
(GS) | 22
(GS) | 20 | 18
(GS) | 16
(GS) | 14
(GS) | 12 | 12
(GS) | 10
(GS) | 8
(GS) | 8 | 7 | 4 | 5
(MM) | 2 | 4 | | 1
|
|---|
| 7 | 49 | 43 | 39
(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
|
|---|
| 8 | 64 | 56
(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
|
|---|
| 9 | 81 | 72 | 64
(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) | | 4 | | 2 | | 1
|
|---|
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
3 × 3 Chessboards
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
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
|
|---|
| 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
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
|
|---|
| 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
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
|
|---|
| 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
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
|
|---|
| 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
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
|
|---|
| 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
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
|
|---|
| 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
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
|
|---|
| 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
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
|
|---|
| 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
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
|
|---|
| 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
ρ = 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
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
|
|---|
| 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.
