Problems & Puzzles: Puzzles

Puzzle 30.- Queen attacking primes in a Knight’s tour solution

G. L. Honaker , Jr. (15/11/98) proposed the following problem to me and to Mike Keith:

"Find the greatest number of prime squares that a queen can command if placed on a nxn knight's tour solution"

The ‘knight's tour’ is a numbered tour of a knight over a otherwise empty nxn board, visiting each square once only.

Very soon Keith succeeded and solved many questions surrounding this puzzle; moreover he has put all his results in the following page:

http://users.aol.com/s6sj7gt/primeq.htm

I recommend to all those programmers and chess lovers not only to visit Keith's beautiful page, but to write your own code for achieving knight's tour solutions.  You are going to have a lot of fun!

Hint: Warnsdorff's rule: "Play the knight to a square where it commands the fewest squares not yet used."

Perhaps you can improve the best solutions for the cases 10 x 10 and higher.  The status of Q(10) is the only perfect configuration not known


Jacques Tramu found (March 28, 2004) a perfect (optimal) solution for the 9x9 board
 

I have found a perfect (optimal) solution for the Honaker problem (Queen attacks primes on a knight's tour) on a 9x9 board . The number of attacked primes is 22 (maximum).

 
Here is the solution :( Q on 55) - Q(9) = 22
 

   13*  76   15   20   11*  74   25   22   09
   16   19*  12   75   26   21   10   67*  24
   77   14   17*  28   73*  56   23*  08   69
   18   81   78   43*  60   27   68   57   66
   79*  44   29*  02* +55+  72   59*  70   07*
   30   51   80   61*  42   03*  36   65   58
   45   48   41*  52   01   54   71*  06   35
   50   31*  46   39   62   33   04   37*  64
   47*  40   49   32   53*  38   63   34   05*
  
 or , more readable, here :
 
 http://mapage.noos.fr/echolalie/q9.htm
 

***

Not far away (April 3, 2004) he also got the next record: a perfect solution for 10x10 board:

Q(10) = 25
Queen on 45 .
 
  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
  
 best viewed here :
  
   http://mapage.noos.fr/echolalie/q10.htm
 
No perfect solutions exist for N > 10 ;
here are some improvements on known solutions :

***

So, the game is over (that is to say, this game is over). Thanks Mr. Tramu. This puzzle, from Honaker, should have been posed in the first year of these pages (1998); accordingly this puzzle lasted 5 years and months to be beaten; nothing bad...

***

 

 


Records   |  Conjectures  |  Problems  |  Puzzles