The Prime Queen Attack ProblemProblem 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

nxnchessboard, 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

perfectknight'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 263564 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 17where 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

nxnboard, withn>5. Denote by Q(n) the maximum number of primes that can be attacked for a givenn.The table below shows the best known (largest) values of Q(n) fornup 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.

nQ( 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 primes3 14 19 24 1 20 9 2 13 18 15 4258 23 10 21 6 17 12 5 16 11 22 7

6x6 board - 11 of 11 primes1 36 15 26 3 6 16 27 2 5 34 25 11 143528 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 primes47 12 39 8 27 14 29 38 9 46 13 30 7 26 45 48 11 40 25 28 15 10 37 24916 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 primes13 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 784360 27 68 57 66 79 44 29 25572 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 primes62 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

nincreases it becomes harder to achieve perfection, and a moment's thought shows why this is the case. Assumenis even (a similar argument works fornodd). 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(n^{2}) primes [the number of primes<n^{2}] 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 annxngrid, as described in the previous paragraph. Then,M(n) = 3n-4 forneven and 4[n/4] + 2n- 1 fornodd. The growth argument means that for allnsufficiently large a perfect attack configuration is impossible. This first happens forn=11, since thenM(n) = 4[n/4] + 2n- 1 = 29 whereas pi(121)=30. So we have:

Theorem:A perfect configuration is impossible forn>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-perfectconfiguration as one that attacks not pi(n) primes but ratherM(n), the maximum amount possible whenn>11. In contrast to perfectness, it should beeasierto be quasi-perfect asnbecomes larger. What, we wonder, is the smallest value ofnfor 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 563562 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 51Some other interesting questions about this problem include:

(1) Are the Q(

n) values forn=10, 11, and 12 shown above really the best possible? What about even largern?

(2) What are the optimum scores for the reentrant version of the problem for variousn?

(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 8122 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 44Although 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.