Proposed by Christian Bessiere

This problem, posed first by G.L. Honaker, is to put a queen and the $n^2$ numbers $1,…,n^2$, on a $n \times n$ chessboard so that:

- no two numbers are on the same cell,
- any number $i+1$ is reachable by a knight move from the cell containing $i$,
- 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.

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 |