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>N2–A.

The 2×2 boards are boring, as each square attacks each other. Thus f(2,Q,A) = N2–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) = N2–3N+2 and f(N,1,1) = N2–4N+4.

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

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

3×3 Board
Q \ A012345678
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 \ A012345678
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 \ A012345678
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 \ A012345678
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 \ A012345678
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 \ A012345678
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 \ A01234567
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 \ A01234567
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.