The Prime Queen Attacking ProblemProblem by G. L. Honaker, Jr.

These notes by Mike Keith, last updated Oct 2023

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 some 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 chess 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 Mike 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 number of attacked primes in the best known solution for a givenn, and let Pr(n) be the number of primes between 1 andn^{2}(i.e., the number of primes on the board). Obviously, Q(n) ≤ Pr(n); if Q(n) = Pr(n) we say thatnhas aperfectsolution, in which all the primes in the grid are attacked.The table below shows the best known (largest) values of Q(

n) fornup to 12. The bold underlined values are perfect solutions, with all primes in the grid being attacked. The last two values of Q(n) are still the best known to me, but it seems plausible that they could be improved.

nQ( n)Pr( n)Discoverer 5 99 Mike Keith, 1998 6 1111 Mike Keith, 1998 7 1515 Mike Keith, 1998 8 1818 Mike Keith, 1998 9 2222 Jacques Tramu, 2004 10 2525 Jacques Tramu, 2004 11 24 30 Jacques Tramu, 2004 12 25 34 Jacques Tramu, 2004 Here are perfect 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 ("00" = 100)Is there a simple reason why perfect solutions haven't been found for

n> 10? The answer is yes:

Theorem:Perfect solutions are impossible whenn≥ 11.

Proof:First, color the board's squares white and black in the usual way (as on a chessboard). Now notice that, due to the properties of the knight's move and the numbering of the tour with successive integers, all black squares (or white squares) on the board have numbers with the same parity (odd or even). Note that all the prime numbers we want the queen to attack are odd numbers, with one exception (the even number 2). Define M(n) as the maximum number of primes that could possibly be attacked by a queen given these parity considerations. This is simply the maximum number of odd numbers we could attack plus one (for the prime 2, which doesn't have to use up one of the odd-number slots). Note that the queen itself will also be located on an odd-numbered square.Without loss of generality we can put the odd numbers on the black squares, then find the best black square to put the queen on to attack as many black squares as possible, and count how many are attacked. In the diagrams below, each X is a black square attacked by the queen (

Q)diagonally, while O is a black square attacked orthogonally. Let X(n) and O(n) represent the number of X's and O's for a givenn.It turns out that there are four cases for the X(n) and O(n) values based on the value ofnmod 4. These four cases are illustrated by the boards forn= 8, 9, 10, and 11, though the formulas work for anyn.Using the values of X(

n) and O(n) given by these diagrams, then computing M(n) = X(n) + O(n) + 1 (again, the +1 comes from the fact that we also attack the even prime 2), the answer simplifies toM(

n) = 3n- 2 if (nmod 4) = 1

3n- 4 otherwiseIf M(

n) < Pr(n) a perfect solution is impossible, since the maximum number of primes we can possibly attack is less than the number of primes we need to attack. Here are the first few values of M(n) and Pr(n) starting atn= 5:

n56789101112131415M( n)13 14 17 20 25 26 29 32 37 38 41 Pr( n)9 11 15 18 22 25 30 34 39 44 48 As indicated by the red numbers, from

n= 11 onward M(n) is less than Pr(n). This will continue for largern,since M(n) grows linearly (it is basically 3n) while Pr(n) has a growth rate ofn^{2}/log(n), which is faster than linear. This completes the proof.A harder version of this problem requires the knight's tour to be closed (reentrant), which means that the last square in the knight's tour is a knight's move away from the first square. In April 1999, "qscgz" (Guenter Stertenbrink) 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 intriguing questions include:

(1) Are the Q(

n) values forn=11, and 12 shown above really the best possible? If they can be improved, how close can we get to M(n)? What about even largern?

(2) Can a closed tour always be found that attacks as many primes as the best open tour on the same board?

(3) Generalize to annxmboard and determine the values of Q(n, m). For which (n, m) values are there perfect solutions?

(4) What are the best solutions using other chess pieces, or pieces from chess variants, instead of the queen?In closing, here is another interesting solution sent to me by George Jelliss. Consider the following 8x8 re-entrant tour, with the queen on 1:

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.