Problems & Puzzles: Puzzles

Puzzle 297. Queens on magic squares

Dear friends:  I will be traveling for the next 15 days through China.  If I can get a stable contact with the server of my site from my laptop, I will try to continue posing puzzles, every Saturday morning. Otherwise, the next puzzle will come the next 15/1/2005. From the bottom of my heart, enjoy this season holydays and receive my very best wishes for the next year, 2005. Thanks for your continuous support participating in this special circle of friends of the prime numbers.

 

Anurag Sahay poses the following puzzle:

Construct a magic square nxn (using the numbers 1 to n2) and place n queens only on these cells which contain prime numbers, such that no queen can take any other queen.

1. What is the smallest magic square (n) having solution?
2. Get one solution for the next three larger magic squares (n+1, n+2 & n+3)
3. Redo the exercises 1 & 2 with one additional condition: "one of the diagonals should also contain prime numbers only".

Sahay shows one example for the question 3 & n=8

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

Queens on bold prime numbers: 23,19,17,53,5,47,31,43.
Primes-Diagonal: from the 61-corner to 7-corner.
Magic sum:260

Contributions came from Jacques Tramu and Luke Pebody.

Jacques Tramu wrote:

Notations :
* = queen location (prime number)
+ = prime number
 
1) minimal solution
n = 4
 
  1  11*  8  14
 16   6   9   3*
 13*  7+ 12   2+
  4  10   5* 15
 
 magic sum : 34
 
2) other solutions n+1, n+2, n+3
 
n =5
 
  2*  1  13  24  25
  4  23  17*  6  15
 20  22  11   9   3*
 21   5*  8  19  12
 18  14  16   7* 10
 
magic sum : 65
 
n= 6
 
  1   2*  3+ 34  35  36
  4  17+ 28  29* 12  21
 10  27  30   5+ 20  19*
 31* 24   9  22  11+ 14
 32  16  23*  8  26   6
 33  25  18  13+  7* 15
 
magic sum : 111
 
n = 7 
 
  2*  1   3+ 25  47+ 48  49    
 42  12  29* 33  39  16   4    
 41+ 32  38  26  13* 20   5+   
 27  35  34  24  18  30   7*   
 10  37* 14  36  31+ 28  19+  
  9  15  40  23* 21  22  45    
 44  43+ 17+  8   6  11* 46    
 
magic sum : 175
 
------------------------------------------------------------
 
3) one diagonal contains primes only
 
3.1) minimal solution
 
n =  5
 
  3* 15  25   8  14
  4   7+ 17* 21  16
 24  20  13+  6   2*
 22   5*  9  19+ 10
 12  18   1  11* 23+
 
 
3.2 ) other solutions n+1, n+2, n+3
 
n = 6 no solution (not enough primes)
 
n = 7
 
 47*  1   2+  4  24  48  49    
  6  43+ 11* 15  44  16  40    
  8  30  41+ 35  13* 27  21    
  9  26  39  29+ 33  20  19*   
 14  37* 12  38   7+ 42  25    
 45  10  34  31* 32   5+ 18    
 46  28  36  23+ 22  17*  3+   
 
n = 8 the published solution

Later he added more on the same:

Solutions for 8x8 magic square:
 
magic sum 260
 
- queens on primes
 
 2*  1   4   58  55  49  59+ 32    
 57  39  42  12   3* 18  48  41+  
 60  54  35  33  36  27  10   5*   
 29+ 51  43+ 61+  9   7* 14  46    
 44   8  11* 37+ 24  21  63  52    
 22  56  50  15  53+ 31+ 13* 20    
  6  17* 47+ 25  64  45  30  26    
 40  34  28  19* 16  62  23+ 38    
 
 
 - queens on primes and primes on diagonal
 
  61*  1   2+ 30  20  42  56  48    
  38  59+ 10  24  11* 63   4  51    
  27  12  53+ 28  50  16  57  17*   
  32  44  39  43+ 15  41*  6  40    
   8  49  19* 45  29+ 46  55   9    
  33  36  60  25  52   7+ 13* 34    
  26  37* 23+ 18  62  31+  5+ 58    
  35  22  54  47* 21  14  64   3+   
 
  ------------------------------------------------
 
Hints for generating magic squares :
- fill the square in this order : col 1, row 1, col 2, row 2, ...
- fill the square with random numbers (1 to n^2) satisfying the constraints (queen on prime, magic sum)
- to speed up the search, pre-compute decomposition tables for all values up to the magic sum .
 
Example :
 
 10 = 1 + 2 + 7
 10 = 1 + 3 + 6
 10 = 1 + 4 + 5
 10 = 2 + 3 + 5
 
IF a row (column, diagonal)
 -has three holes, (three cells to fill)
 -and its value is  ( magic sum - 10),
 - and numbers 1 and 2 are already used,
  THEN the search can be cut (no possible solution).
  
Tables are computed for 2, 3 and 4 holes.(677040 entries for 8x8 magic square),
stored as trees for fast access.
Search duration is a few seconds for a 8x8 magic square.
 
See also  http://www.trump.de/magic-squares/howmany.html

***

Luke Pebody wrote:

There are two solutions, allowing for the 16 symmetries of magic 4x4 squares.

The solutions are:
14 3 8 9
2 15 12 5
11 6 1 16
7 10 13 4

and

14 3 2 15
8 9 12 5
11 6 7 10
1 16 13 4,

with the queens on 3,5,11,13.

N=5:

05 03 25 08 24
21 23 04 15 02
16 20 13 06 10
11 01 14 17 22
12 18 09 19 07

Put the queens on 3,2,13,11,19.
Note that the TL-BR diagonal is all prime.

 

***

A few days later Mr. Tramu sent another 'large' solution 'just for fun':

Magic sum = 1695
 
 223*   1    2+ 120  212  213  224   12  148  160  172   90   47+  29+  42
 58  211+  17* 182  169  192  178   85  111  122  106  139+  75    4   46
 73+ 114  199+  86   31*  98  198   99   64  225   36   28   65  174  205
188   19* 146  197+  69   91   67+ 183   43+  55   30  214   10  187  196
108  210  189  167+ 193+  49   68   79+ 147   41* 201   21  112   70   40
130   38  204  195  100  191+  80   92   77   39   24   83* 123  184  135
 14  149+  16  132  101+  33  181+ 136   87  125   60  216  218  173*  54
 74  177   66   37* 119  121  141  179+  78  165   81   25  217   45  170
180   84  155  162  117  163+ 127+  27   59+ 176  186   26   53*  35  145
154  215   63   48  126  166   22  138  109*  23+   9   95  185  208  134
 15    6  194   20   71+  97*  44  175  168  171   13+ 202  158  209  152
159   76    8  142  144   18   56  207  219   51  220   11+ 143  128  113*
 72  164  118   52   32   82  103*  89+  62  203  200  221    7+ 140  150
131+ 124  157+  94  115   88   50   57  133  105  151* 222  153    5+ 110
116  107+ 161   61+  96   93  156  137* 190   34  206  102  129  104    3+

 

***

 
Records   |  Conjectures  |  Problems  |  Puzzles