prob029: Prime queen attacking problem

proposed by

Specification

This problem, posed first by G.L. Honaker, is to put a queen and the n^2 numbers 1,...,n^2, on a n x n chessboard so that: (a) no two numbers are on the same cell, (b) any number i+1 is reachable by a knight move from the cell containing i, (c) the number of "free" primes (i.e., primes not attacked by the queen) is minimal. Note that 1 is not prime, and that the queen does not attack its own cell.

Example of solution

A 6x6 chessboard without free primes (the queen is on the cell containing 33):

-------------------
| 9|32| 3|28|11|30|
-------------------
| 4|27|10|31|34| 1|
-------------------
|17| 8|33| 2|29|12|
-------------------
|26| 5|16|19|22|35|
-------------------
|15|18| 7|24|13|20|
-------------------
| 6|25|14|21|36|23|
-------------------

Back