Problems & Puzzles: Puzzles

Puzzle 216. Primes in a square array

Here  you are asked to distribute orderly a prime in a square array such that the rows, the columns and the downward diagonals are distinct prime numbers.

Example:

Please notice that all the primes are distinct and that no zeros are allowed

Questions:

1. Find a solution for a 10x10 square array
2. Find a Titanic solution (nxn square array, n>32)

Solution:

J. K Andersen found a solution for each of the two asked questions:

My program is not efficient and needed 16 hours to find the 33x33 solution
with probable primes. It could be optimized a lot but this was not necessary.
It searches for one prime at a time by placing digits in the empty positions,
starting with the most significant. If a prime cannot be generated, the
program backtracks to change the latest placed digits.

The program first finds random primes with only digits 1,3,7,9 for the bottom
row and right column. Then the diagonals are made prime with random digits
(avoiding 0 as asked). Next it alternates making primes: row 1, column 1, row
2, column 2, ... The final placed digit must generate 3 simultaneous primes,
including the one with n*n digits which is tested last. It took around 2200
composites (twice the expectation) before this was a 1089-digit prime.
 

***

J. K. Andersen found (17/4/03) a beautiful additional solution for the 10x010 case:

***

And now a 33x33 solution with an extra condition: All 33-digit numbers are distinct REVERSIBLE primes, by J. K. Andersen...again:

After implementing and optimizing a new algorithm, it only took 15 hours to find a 33x33 square with distinct reversible primes:

313991399371199131139799331911377
147529895941991587879456361416793
343797754289852575517133312684269
943695978946644516863648961536981
354977375935673418795287369494189
373478623641239162919379269294319
941871985794933399739235523691657
154837889117834232678974449658279
117129522895488222612449716435651
112797868118722475112367318718359
954332756851152845673554343833423
958324129279242571543956244312159
149656971499164148747227159798119
915531789396889314926554998567389
189177184378411356887579966732519
395769634484946484155736859195773
976485587598811713196922772648319
742413259665798111566314845954551
344321292792178583218155711143611
735499324729469232679643212644511
755544726594454683193623626957711
324895114496128478896375157597659
974246467315936911531792288239249
136494329788845728831611728857639
343337449493221561738959339141347
119138332653219119612984163669317
356624631952956188127648784846583
361813646131913157456632928169513
747231224138425962243343371145487
745954412587484837933238642278851
955148574512595199969685612245439
118737626399742196143742577819117
917319979999777371311371999793393

First my program easily (in a second) found a partial solution missing 7 rows and 7 columns, crossing in a 7x7 empty square away from the diagonals and edges.
For each of the 14 remaining numbers, all 9^7 7-digit sequences (without 0's as requested) were tested. Those making a reversible 33-digit prime in the partial solution were stored in a table with around 8800 sequences per number.
Then it was basically a crossword puzzle combining digits instead of letters in the 7x7 square. This was the computationally hard part. The 624th solution yielded a 1089-digit probable prime, proved with Primo.