Problem of the Month (September 2016)

On an N×N chessboard, when we place Q queens, what is the maximum number of squares that can be attacked exactly A times?

ANSWERS

George Sicherman sent solutions.

Let f(N,Q,A) denote the largest number of squares that are attacked exactly A times. Clearly f(N,Q,A) = 0 if Q<A or Q>N²–A.

The 2×2 boards are boring, as each square attacks each other. Thus f(2,Q,A) = N²–Q when Q=A, and 0 otherwise.

The boards containing one piece are also boring, as a queen on the edge of the board attacks the fewest squares, and a queen in the middle of the board attacks the most squares. Thus f(N,1,0) = N²–3N+2 and f(N,1,1) = N²–4N+4.

Computer evidence suggests the following formulas. Can you prove any of them? What other patterns can you find?

f(N,2,0) = N²–5N+7
f(N,2,1) = 7N–18 (for N≥6)
f(N,2,2) = 12 (for N≥8)
f(N,3,0) = N²–6N+9 (for N≥6)
f(N,3,3) = 5 (for N≥4)
f(N,4,0) = 4 (N–3)/2 (N–2)/2 (for N≥5)
f(N,4,2) = 6N–12 (for even N)
f(N,4,3) = 14 (for N≥6)
f(N,4,4) = 4 (for N≥4)
f(N,5,1) = 9N–31 (for N≥4)
f(N,5,4) = 8 (for N≥5)
f(N,5,5) = 3 (for N≥5)
f(N,6,5) = 4 (for N≥4)
f(N,6,6) = 2 (for N≥4)

Here are the best known solutions. A yellow background means all vacant squares are attacked A times.

3×3 Board

Q \ A	0	1	2	3	4	5	6	7	8
2	1 square 2 solutions	5 squares 1 solution	5 squares 1 solution
3		3 squares 1 solution	5 squares 1 solution	4 squares 2 solutions
4		1 square 3 solutions	4 squares 4 solutions	5 squares 2 solutions	2 squares 3 solutions
5			3 squares 1 solution	4 squares 4 solutions	2 squares 3 solutions	2 squares 1 solution
6			2 squares 2 solutions	3 squares 2 solutions	2 squares 4 solutions	1 square 3 solutions	1 square 6 solutions
7				2 squares 2 solutions	2 squares 1 solution	2 squares 1 solution		1 square 2 solutions
8				1 square 1 solution		1 square 1 solution			1 square 1 solution

4×4 Board

Q \ A	0	1	2	3	4	5	6	7	8
2	3 squares 2 solutions	12 squares 1 solution	7 squares 3 solutions
3	2 squares 2 solutions	10 squares 1 solution	10 squares 1 solution	5 squares 2 solutions
4	1 square 25 solutions	8 squares 1 solution	12 squares 1 solution	9 squares 1 solution	4 squares 1 solution
5	1 square 9 solutions	5 squares 2 solutions	11 squares 1 solution	10 squares 1 solutions	6 squares 2 solutions	2 squares 8 solutions
6	1 square 2 solutions	4 squares 1 solution	8 squares 2 solutions	10 squares 1 solution	6 squares 17 solutions	4 squares 2 solutions	2 squares 2 solutions
7		3 squares 1 solution	6 squares 10 solutions	9 squares 2 solutions	7 squares 4 solutions	5 squares 3 solutions	2 squares 32 solutions	1 square 29 solutions
8		1 square 26 solutions	6 squares 2 solutions	8 squares 2 solutions	8 squares 1 solution	8 squares 1 solution	4 squares 1 solutions	2 squares 5 solutions	1 square 6 solutions
9		1 square 3 solutions	4 squares 8 solutions	7 squares 2 solutions	7 squares 1 solution	6 squares 1 solution	4 squares 2 solutions	3 squares 1 solution	1 square 23 solutions
10			4 squares 1 solution	6 squares 3 solutions	6 squares 1 solution	5 squares 1 solution	3 squares 12 solutions	4 squares 1 solution	2 squares 2 solutions
11			3 squares 1 solution	5 squares 2 solutions	5 squares 1 solution	4 squares 7 solutions	3 squares 1 solution	3 squares 5 solutions	2 squares 5 solutions
12			2 squares 2 solutions	4 squares 3 solutions	4 squares 2 solutions	4 squares 4 solutions	2 squares 5 solutions	3 squares 1 solution	4 squares 1 solution
13				3 squares 2 solutions	2 squares 10 solutions	3 squares 4 solutions	1 square 6 solutions	2 squares 3 solutions	3 squares 1 solution
14				2 squares 2 solutions	2 squares 1 solution	2 squares 5 solutions		1 square 3 solutions	2 squares 2 solutions
15				1 square 1 solution		1 square 1 solution			1 square 1 solution

5×5 Board

Q \ A	0	1	2	3	4	5	6	7	8
2	7 squares 4 solutions	19 squares 1 solution	9 squares 1 solution
3	5 squares 1 solution	17 squares 1 solution	16 squares 1 solution	5 squares 15 solutions
4	4 squares 6 solutions	15 squares 2 solutions	18 squares 1 solution	13 squares 1 solution	4 squares 2 solutions
5	3 squares 1 solution	14 squares 1 solution	20 squares 1 solution	14 squares 7 solutions	8 squares 1 solution	3 squares 2 solutions
6	2 squares 38 solutions	12 squares 2 solutions	17 squares 2 solutions	17 squares 1 solution	9 squares 8 solutions	4 squares 7 solutions	2 squares 8 solutions
7	2 squares 4 solutions	10 squares 1 solution	15 squares 2 solutions	17 squares 2 solutions	12 squares 8 solutions	6 squares 14 solutions	2 squares 437 solutions	1 square 367 solutions
8	1 square 1056 solutions	8 squares 1 solution	13 squares 9 solutions	16 squares 3 solutions	14 squares 1 solution	8 squares 1 solution	5 squares 1 solution	2 squares 36 solutions	1 square 99 solutions
9	1 square 450 solutions	6 squares 2 solutions	13 squares 1 solution	16 squares 2 solutions	16 squares 1 solution	9 squares 6 solutions	6 squares 4 solutions	4 squares 1 solution	1 square 898 solutions
10	1 square 140 solutions	5 squares 1 solution	10 squares 14 solutions	15 squares 1 solution	15 squares 1 solution	11 squares 4 solutions	7 squares 1 solution	4 squares 10 solutions	2 squares 20 solutions
11	1 square 24 solutions	4 squares 1 solution	10 squares 1 solution	14 squares 2 solutions	14 squares 2 solutions	12 squares 2 solutions	7 squares 20 solutions	5 squares 17 solutions	2 squares 248 solutions
12	1 square 3 solutions	3 squares 9 solutions	9 squares 1 solution	13 squares 2 solutions	13 squares 2 solutions	11 squares 9 solutions	8 squares 5 solutions	7 squares 2 solutions	4 squares 3 solutions
13		3 squares 1 solution	8 squares 16 solutions	12 squares 2 solutions	12 squares 2 solutions	12 squares 2 solutions	8 squares 6 solutions	7 squares 10 solutions	4 squares 20 solutions
14		1 square 404 solutions	8 squares 1 solution	11 squares 2 solutions	11 squares 2 solutions	11 squares 1 solution	7 squares 15 solutions	7 squares 21 solutions	6 squares 2 solutions
15		1 square 54 solutions	6 squares 2 solutions	10 squares 3 solutions	10 squares 3 solutions	10 squares 2 solutions	6 squares 56 solutions	7 squares 11 solutions	6 squares 9 solutions
16		1 square 4 solutions	5 squares 1 solution	9 squares 3 solutions	9 squares 3 solutions	9 squares 4 solutions	6 squares 1 solution	6 squares 99 solutions	9 squares 1 solution
17			4 squares 13 solutions	8 squares 4 solutions	8 squares 2 solutions	8 squares 14 solutions	5 squares 7 solutions	6 squares 14 solutions	8 squares 3 solutions
18			4 squares 1 solution	7 squares 4 solutions	7 squares 2 solutions	7 squares 28 solutions	4 squares 12 solutions	5 squares 54 solutions	7 squares 8 solutions
19			3 squares 1 solution	6 squares 4 solutions	6 squares 1 solution	6 squares 47 solutions	3 squares 58 solutions	5 squares 2 solutions	6 squares 16 solutions
20			2 squares 2 solutions	5 squares 2 solutions	5 squares 1 solution	5 squares 53 solutions	3 squares 5 solutions	4 squares 4 solutions	5 squares 23 solutions
21				4 squares 3 solutions	4 squares 2 solutions	4 squares 48 solutions	2 squares 4 solutions	3 squares 7 solutions	4 squares 23 solutions
22				3 squares 2 solutions	2 squares 15 solutions	3 squares 25 solutions	1 square 8 solutions	2 squares 7 solutions	3 squares 16 solutions
23				2 squares 2 solutions	2 squares 1 solution	2 squares 11 solutions		1 square 5 solutions	2 squares 8 solutions
24				1 square 1 solution		1 square 2 solutions			1 square 3 solutions

6×6 Board

Q \ A	0	1	2	3	4	5	6	7	8
2	13 squares 3 solutions	24 squares 1 solution	10 squares 3 solutions
3	9 squares 9 solutions	26 squares 1 solution	19 squares 2 solutions	5 squares 34 solutions
4	8 squares 2 solutions	24 squares 1 solution	24 squares 1 solution	14 squares 1 solution	4 squares 5 solutions
5	6 squares 3 solutions	23 squares 1 solution	24 squares 3 solutions	18 squares 3 solutions	8 squares 1 solution	3 squares 4 solutions
6	5 squares 3 solutions	21 squares 3 solutions	28 squares 2 solutions	22 squares 4 solutions	12 squares 5 solutions	4 squares 27 solutions	2 squares 24 solutions
7	4 squares 13 solutions (GS)	20 squares 1 solution (GS)	23 squares 9 solutions (GS)	24 squares 2 solutions (GS)	16 squares 2 solutions (GS)	7 squares 4 solutions (GS)	2 squares 2819 solutions (GS)	1 square 2444 solutions (GS)
8	4 squares 2 solutions (GS)	18 squares 1 solution (GS)	23 squares 1 solution (GS)	25 squares 1 solution (GS)	24 squares 1 solution (GS)	10 squares 2 solutions (GS)	5 squares 2 solutions (GS)	2 squares 213 solutions (GS)	1 square 652 solutions (GS)
9	3 squares 9 solutions (GS)	17 squares 1 solution (GS)	21 squares 2 solutions (GS)	26 squares 1 solution (GS)	24 squares 1 solution (GS)	12 squares 1 solution (GS)	6 squares 27 solutions (GS)	4 squares 1 solution (GS)	1 square 13314 solutions (GS)
10	2 squares 1736 solutions (GS)	14 squares 2 solutions (GS)	20 squares 1 solution (GS)	25 squares 1 solution (GS)	23 squares 2 solutions (GS)	14 squares 2 solutions (GS)	8 squares 9 solutions (GS)	4 squares 65 solutions (GS)	2 squares 157 solutions (GS)
11	2 squares 379 solutions (GS)	12 squares 2 solutions (GS)	18 squares 1 solution (GS)	25 squares 1 solution (GS)	23 squares 1 solution (GS)	16 squares 2 solutions (GS)	10 squares 2 solutions (GS)	5 squares 2 solutions (GS)	2 squares 4442 solutions (GS)
12	2 squares 53 solutions (GS)	10 squares 2 solutions (GS)	17 squares 2 solutions (GS)	24 squares 1 solution (GS)	24 squares 2 solutions (GS)	19 squares 2 solutions (GS)	12 squares 1 solution (GS)	6 squares 2 solutions (GS)	2 squares 15 solutions (GS)
13	2 squares 3 solutions (GS)	8 squares 5 solutions (GS)	15 squares 59 solutions (GS)	23 squares 1 solution (GS)	23 squares 2 solutions (GS)	19 squares 6 solutions (GS)	12 squares 6 solutions (GS)	8 squares 35 solutions (GS)	4 squares 282 solutions (GS)
14	1 square 101632 solutions (GS)	7 squares 2 solutions (GS)	15 squares 5 solutions (GS)	22 squares 2 solutions (GS)	22 squares 6 solutions (GS)	20 squares 3 solutions (GS)	13 squares 7 solutions (GS)	11 squares 1 solution (GS)	6 squares 9 solutions (GS)
15	1 square 39992 solutions (GS)	6 squares 4 solutions (GS)	14 squares 10 solutions (GS)	21 squares 2 solutions (GS)	21 squares 4 solutions (GS)	20 squares 2 solutions (GS)	13 squares 19 solutions (GS)	12 squares 2 solutions (GS)	6 squares 173 solutions (GS)
16	1 square 12370 solutions (GS)	5 squares 16 solutions (GS)	14 squares 1 solution (GS)	20 squares 1 solution (GS)	20 squares 5 solutions (GS)	20 squares 9 solutions (GS)	14 squares 1 solution (GS)	12 squares 34 solutions (GS)	9 squares 2 solutions (GS)
17	1 square 2877 solutions (GS)	5 squares 1 solution (GS)	13 squares 1 solution (GS)	18 squares 25 solutions (GS)	19 squares 5 solutions (GS)	19 squares 3 solutions (GS)	13 squares 22 solutions (GS)	13 squares 4 solutions (GS)	9 squares 23 solutions (GS)
18	1 square 482 solutions (GS)	4 squares 2 solutions (GS)	12 squares 2 solutions (GS)	18 squares 3 solutions (GS)	18 squares 5 solutions (GS)	18 squares 1 solution (GS)	13 squares 3 solutions (GS)	13 squares 6 solutions (GS)	12 squares 2 solutions (GS)
19	1 square 50 solutions (GS)	3 squares 128 solutions (GS)	11 squares 3 solutions (GS)	17 squares 1 solution (GS)	17 squares 6 solutions (GS)	17 squares 2 solutions (GS)	12 squares 26 solutions (GS)	13 squares 2 solutions (GS)	12 squares 10 solutions (GS)
20	1 square 3 solutions (GS)	3 squares 4 solutions (GS)	10 squares 143 solutions (GS)	16 squares 3 solutions (GS)	16 squares 4 solutions (GS)	16 squares 9 solutions (GS)	12 squares 1 solution (GS)	12 squares 82 solutions (GS)	16 squares 1 solution (GS)
21		3 squares 1 solution (GS)	10 squares 12 solutions (GS)	15 squares 4 solutions (GS)	15 squares 3 solutions (GS)	15 squares 16 solutions (GS)	11 squares 2 solutions (GS)	12 squares 5 solutions (GS)	15 squares 3 solutions (GS)
22		1 squares 8683 solution (GS)	10 squares 1 solution (GS)	14 squares 2 solutions (GS)	14 squares 5 solutions (GS)	14 squares 49 solutions (GS)	10 squares 5 solutions (GS)	11 squares 67 solutions (GS)	14 squares 21 solutions (GS)
23		1 squares 1110 solution (GS)	8 squares 1 solution (GS)	13 squares 5 solutions (GS)	13 squares 2 solutions (GS)	13 squares 113 solutions (GS)	9 squares 7 solutions (GS)	11 squares 1 solution (GS)	13 squares 77 solutions (GS)
24		1 squares 92 solution (GS)	6 squares 3 solutions (GS)	12 squares 6 solutions (GS)	12 squares 4 solutions (GS)	12 squares 249 solutions (GS)	8 squares 21 solutions (GS)	10 squares 8 solutions (GS)	12 squares 252 solutions (GS)
25		1 squares 4 solution (GS)	5 squares 28 solutions (GS)	11 squares 4 solutions (GS)	11 squares 2 solutions (GS)	11 squares 413 solutions (GS)	7 squares 79 solutions (GS)	9 squares 40 solutions (GS)	11 squares 567 solutions (GS)
26			5 squares 1 solution (GS)	10 squares 5 solutions (GS)	10 squares 3 solutions (GS)	10 squares 630 solutions (GS)	7 squares 2 solutions (GS)	8 squares 151 solutions (GS)	10 squares 1051 solutions (GS)
27			4 squares 16 solutions (GS)	9 squares 4 solutions (GS)	9 squares 2 solutions (GS)	9 squares 777 solutions (GS)	6 squares 4 solutions (GS)	7 squares 330 solutions (GS)	9 squares 1465 solutions (GS)
28			4 squares 1 solution (GS)	8 squares 4 solutions (GS)	8 squares 1 solution (GS)	8 squares 866 solutions (GS)	5 squares 7 solutions (GS)	7 squares 2 solutions (GS)	8 squares 1674 solutions (GS)
29			3 squares 1 solution (GS)	7 squares 4 solutions (GS)	7 squares 2 solutions (GS)	7 squares 784 solutions (GS)	4 squares 49 solutions (GS)	6 squares 5 solutions (GS)	7 squares 1465 solutions (GS)
30			2 squares 2 solutions (GS)	6 squares 4 solutions (GS)	6 squares 1 solution (GS)	6 squares 634 solutions (GS)	4 squares 3 solutions (GS)	5 squares 8 solutions (GS)	6 squares 1051 solutions (GS)
31				5 squares 2 solutions (GS)	5 squares 1 solution (GS)	5 squares 385 solutions (GS)	3 squares 3 solutions (GS)	4 squares 11 solutions (GS)	5 squares 567 solutions (GS)
32				4 squares 3 solutions (GS)	4 squares 2 solutions (GS)	4 squares 198 solutions (GS)	2 squares 5 solutions (GS)	3 squares 11 solutions (GS)	4 squares 252 solutions (GS)
33				3 squares 2 solutions (GS)	2 squares 21 solutions (GS)	3 squares 63 solutions (GS)	1 squares 9 solutions (GS)	2 squares 9 solutions (GS)	3 squares 77 solutions (GS)
34				2 squares 2 solutions (GS)	2 squares 1 solution (GS)	2 squares 19 solutions (GS)		1 squares 6 solutions (GS)	2 squares 21 solutions (GS)
35				1 square 1 solution (GS)		1 square 2 solutions (GS)			1 square 3 solutions (GS)

7×7 Board

Q \ A	0	1	2	3	4	5	6	7	8
2	21 squares 6 solutions	31 squares 1 solutions	11 squares 2 solutions
3	16 squares 5 solutions	34 squares 1 solution	22 squares 3 solutions	5 squares 77 solutions
4	16 squares 1 solution	34 squares 1 solution	29 squares 1 solution	14 squares 3 solutions	4 squares 11 solutions
5	11 squares 1 solution	32 squares 5 solutions	33 squares 1 solution	21 squares 2 solutions	8 squares 4 solutions	3 squares 11 solutions
6	10 squares 1 solution (GS)	32 squares 1 solution (GS)	34 squares 5 solutions (GS)	28 squares 1 solution (GS)	12 squares 16 solutions (GS)	4 squares 65 solutions (GS)	2 squares 69 solutions (GS)
7	7 squares 38 solutions (GS)	30 squares 7 solutions (GS)	38 squares 2 solutions (GS)	33 squares 1 solution (GS)	16 squares 31 solutions (GS)	7 squares 18 solutions (GS)	2 squares 12279 solutions (GS)	1 square 12508 solutions (GS)
8	6 squares 174 solutions (GS)	30 squares 1 solution (GS)	40 squares 1 solution (GS)	33 squares 1 solution (GS)	25 squares 1 solution (GS)	10 squares 9 solutions (GS)	5 squares 7 solutions (GS)	2 squares 831 solutions (GS)	1 square 4030 solutions (GS)
9	6 squares 19 solutions (GS)	28 squares 1 solution (GS)	40 squares 1 solution (GS)	35 squares 1 solution (GS)	29 squares 1 solution (GS)	12 squares 47 solutions (GS)	6 squares 102 solutions (GS)	4 squares 4 solutions (GS)	1 square 123279 solutions (GS)
10	6 squares 1 solution (GS)	26 squares 2 solutions (GS)	29 squares 5 solutions (GS)	36 squares 1 solution (GS)	31 squares 2 solutions (GS)	16 squares 3 solutions (GS)	9 squares 4 solutions (GS)	4 squares 256 solutions (GS)	2 squares 909 solutions (GS)

8×8 Board

Q \ A	0	1	2	3	4	5	6	7	8
2	31 squares 6 solutions	38 squares 1 solution	12 squares 2 solutions
3	25 squares 3 solutions	43 squares 3 solutions	23 squares 5 solutions	5 squares 124 solutions
4	24 squares 1 solution	46 squares 1 solution	36 squares 1 solution	14 squares 7 solutions	4 squares 22 solutions
5	17 squares 2 solutions	43 squares 3 solutions	39 squares 2 solutions	22 squares 5 solutions	8 squares 5 solutions	3 squares 16 solutions
6	15 squares 2 solutions (GS)	43 squares 1 solution (GS)	34 squares 1 solution (GS)	31 squares 1 solution (GS)	12 squares 36 solutions (GS)	4 squares 133 solutions (GS)	2 squares 138 solutions (GS)
7	13 squares 1 solution (GS)	41 squares 11 solutions (GS)	44 squares 3 solutions (GS)	38 squares 1 solution (GS)	17 squares 4 solutions (GS)	7 squares 47 solutions (GS)	2 squares 40573 solutions (GS)	1 square 48799 solutions (GS)
8	11 squares 7 solutions (GS)	41 squares 2 solutions (GS)	48 squares 4 solutions (GS)	41 squares 9 solutions (GS)	25 squares 1 solution (GS)	10 squares 33 solutions (GS)	5 squares 11 solutions (GS)	2 squares 2655 solutions (GS)	1 square 17442 solutions (GS)

9×9 Board

Q \ A	0	1	2	3	4	5	6	7
2	43 squares 10 solutions	45 squares 1 solution	12 squares 4 solutions
3	36 squares 4 solutions	54 squares 3 solutions	25 squares 6 solutions	5 squares 219 solutions
4	36 squares 1 solution	56 squares 2 solutions	40 squares 1 solution	14 squares 12 solutions	4 squares 36 solutions
5	27 squares 1 solution (GS)	56 squares 5 solutions (GS)	52 squares 1 solution (GS)	23 squares 4 solutions (GS)	8 squares 11 solutions (GS)	3 squares 31 solutions (GS)
6	24 squares 1 solution (GS)	55 squares 1 solution (GS)	52 squares 1 solution (GS)	33 squares 2 solutions (GS)	12 squares 66 solutions (GS)	4 squares 232 solutions (GS)	2 squares 299 solutions (GS)
7	20 squares 5 solutions (GS)	53 squares 19 solutions (GS)	53 squares 3 solutions (GS)	42 squares 4 solutions (GS)	18 squares 8 solutions (GS)	7 squares 97 solutions (GS)	2 squares 112572 solutions (GS)	1 square 161826 solutions (GS)

10×10 Board

Q \ A	0	1	2	3	4	5	6	7
2	57 squares 10 solutions	52 squares 1 solution	12 squares 8 solutions
3	49 squares 3 solutions	65 squares 2 solutions	26 squares 11 solutions	5 squares 316 solutions
4	48 squares 1 solution (GS)	72 squares 1 solution (GS)	48 squares 1 solution (GS)	14 squares 20 solutions (GS)	4 squares 60 solutions (GS)
5	37 squares 1 solution (GS)	74 squares 1 solution (GS)	56 squares 2 solutions (GS)	23 squares 10 solutions (GS)	8 squares 14 solutions (GS)	3 squares 40 solutions (GS)
6	33 squares 1 solution (GS)	72 squares 1 solution (GS)	64 squares 1 solution (GS)	34 squares 3 solutions (GS)	12 squares 110 solutions (GS)	4 squares 370 solutions (GS)	2 squares 497 solutions (GS)
7	30 squares 2 solutions (GS)	67 squares 7 solutions (GS)	65 squares 1 solution (GS)	44 squares 7 solutions (GS)	18 squares 20 solutions (GS)	7 squares 164 solutions (GS)	2 squares 272297 solutions (GS)	1 square 462795 solutions (GS)

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