The Prime Queen Attack Problem

Problem by G. L. Honaker, Jr.
These notes by Mike Keith, last updated May 2004


 

This interesting problem was posed by G. L. Honaker, Jr. in November of 1998. First, create any knight's tour on an n x n chessboard, in which the knight starts on any square of the board and by successive knight's moves visits every square on the board exactly once. Number the squares visited by the knight in order starting with 1 for the starting square. When you are done, place a Queen on any square and count the number of prime numbers attacked by the Queen (note that the Queen is not considered to be attacking the square it sits on).

Now, the problem: What is the largest number of primes that can be attacked by the Queen, for any placement of the Queen and any knight's tour?

First, note that there are 18 primes between 1 and 64. Amazingly, there is a perfect knight's tour in which all 18 primes can be attacked! Here is the first perfect solution ever constructed (by M. Keith, in Nov. 1998):

37 24 45  4 39 22 47 62
44  5 38 23 46 61 40 21
25 36 43 60  3 20 63 48
 6 59 26 35 64 41  2 19
27 30 57 42  1 34 49 12
58  7 54 29 52 13 18 15
31 28  9 56 33 16 11 50
 8 55 32 53 10 51 14 17

where the location of the Queen is in blue and the attacked primes are shown in red.

Knights tours are impossible on 1x1, 2x2, 3x3, 4x4 boards, but it is natural to ask the same question for any n x n board, with n > 5.  Denote by Q(n) the maximum number of primes that can be attacked for a given n.  The table below shows the best known (largest) values of Q(n) for n up to 12.  Those shown in green are perfect solutions, with all primes in the grid being attacked.  The other three values of Q(n) are the best known as of 2004.

n   Q(n)   Tot. primes  Discoverer
5   9   9 M. Keith, 1998
6   11   11 M. Keith, 1998
7   15   15 M. Keith, 1998
8   18   18 M. Keith, 1998
9   22   22 Jacques Tramu, 2004
10   25   25 Jacques Tramu, 2004
11   24   30 Jacques Tramu, 2004
12   25   34 Jacques Tramu, 2004

Here are the best known solutions for n=5, 6, 7, 9 and 10 (n=8 is shown above, of course):

5x5 board - 9 of 9 primes

 3 14 19 24  1 
20  9  2 13 18 
15  4 25  8 23 
10 21  6 17 12 
 5 16 11 22  7 

6x6 board - 11 of 11 primes

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

7x7 board - 15 of 15 primes

47 12 39  8 27 14 29
38  9 46 13 30  7 26
45 48 11 40 25 28 15
10 37  2 49 16 31  6
 1 44 17 34 41 24 21
36  3 42 19 22  5 32
43 18 35  4 33 20 23

9x9 board - 22 of 22 primes

13 76 15 20 11 74 25 22  9
16 19 12 75 26 21 10 67 24
77 14 17 28 73 56 23  8 69
18 81 78 43 60 27 68 57 66
79 44 29  2 55 72 59 70  7
30 51 80 61 42  3 36 65 58
45 48 41 52  1 54 71  6 35
50 31 46 39 62 33  4 37 64
47 40 49 32 53 38 63 34  5

10x10 board - 25 of 25 primes

62 21 60 75 64 87 84 77 80 89
19 24 63 86 59 76 65 88 83 78
22 61 20 01 74 85 58 79 90 81
25 18 23 46 43 66 73 82 57 54
36 39 44 67 02 47 42 55 94 91
17 26 37 40 45 72 03 92 53 56
38 35 70 11 68 41 48 95 04 93
27 16 29 32 71 12 07 52 99 96
34 31 14 69 10 49 98 05 08 51
15 28 33 30 13 06 09 50 97 00

(here "00" = 100)

The table above seems to indicate that as n increases it becomes harder to achieve perfection, and a moment's thought shows why this is the case. Assume n is even (a similar argument works for n odd). Since the black squares (or white squares) on the chessboard always contain numbers of with the same parity, due to the properties of a knight's tour, the most odd numbers that can be attacked by a Queen is 3n-5, which happens when the Queen sits on one of the two central odd numbers. If all of these were primes, and if the Queen also attacked the prime 2, then there could be at most 3n-4 primes attacked. On the other hand, there are pi(n2) primes [the number of primes < n2] in the array. This grows faster than linearly, so it becomes harder and harder to reach, since 3n-4 grows linearly.

Denote by M(n) the most number of primes that could ever be attacked in an n x n grid, as described in the previous paragraph. Then, M(n) = 3n-4 for n even and 4[n/4] + 2n - 1 for n odd. The growth argument means that for all n sufficiently large a perfect attack configuration is impossible. This first happens for n=11, since then M(n) = 4[n/4] + 2n - 1 = 29 whereas pi(121)=30. So we have:

Theorem: A perfect configuration is impossible for n > 11.

This theorem, plus the results of Jacques Tramu in 2004, means that we know the answer to the basic question about this problem: Perfect configurations are possible only for n=5,6,7,8,9, and 10.

We can define a quasi-perfect configuration as one that attacks not pi(n) primes but rather M(n), the maximum amount possible when n > 11. In contrast to perfectness, it should be easier to be quasi-perfect as n becomes larger. What, we wonder, is the smallest value of n for which a quasi-perfect configuration is possible?

A harder version of this problem is to require the knight's tour to be closed (reentrant), which means it is possible to step from square 64 back to square 1 with a knight's move. In April 1999, qscgz@aol.com found the first perfect reentrant 8x8 solution:

19 58 33  6 21 16 13  8
32  5 20 17 34  7 22 15
57 18 59  4 29 14  9 12
42 31 56 35 62 11 28 23
55 60 43 30  3 24 63 10
44 41 46 61 36 27 50 25
47 54 39  2 49 52 37 64
40 45 48 53 38  1 26 51

Some other interesting questions about this problem include:

(1) Are the Q(n) values for n=10, 11, and 12 shown above really the best possible?  What about even larger n?
(2) What are the optimum scores for the reentrant version of the problem for various n?
(3) What's the best score attainable for other chess pieces, or pieces from chess variants?

In closing, here is another interesting variation sent to me by George Jelliss. Consider the following re-entrant tour:

 4  7 10 23 64 19 12 15
 9 24  5 18 11 14 63 20
 6  3  8  1 22 61 16 13
25 30 37 60 17 50 21 62
36 59  2 29 42 53 46 51
31 26 33 38 49 40 43 54
58 35 28 41 56 45 52 47
27 32 57 34 39 48 55 44

Although the queen on square 1 only attacks 17 of the 18 primes, this tour has a property not present in any of the 18-attacking tours above, which is that all 17 odd primes are attacked, and every odd number attacked by the queen is a prime.