P1549 [NOIP 1997 Senior] Chessboard Problem

NOIP 1997 Senior, Problem 1. [P5512](https://www.luogu.com.cn/problem/P5512) is the enhanced testdata version of this problem. The actual constraints for this problem are $1\le N\le 5$. There is no guarantee that a solution without hardcoding can pass the original constraints.

On an $N \times N$ ($1 \le N \le 10$) board, fill in the $N ^ 2$ numbers $1, 2, \dots, N ^ 2$, so that the sum of any two adjacent numbers is a prime number. For example, when $N = 2$, there is: | $1$ | $2$ | | :-----------: | :-----------: | | $4$ | $3$ | The adjacent pairs whose sums are prime are: $1+2,1+4,4+3,2+3$ When $N=4$, one possible arrangement is: | $1$ | $2$ | $11$ | $12$ | | :-----------: | :-----------: | :-----------: | :-----------: | | $16$ | $15$ | $8$ | $5$ | | $13$ | $4$ | $9$ | $14$ | | $6$ | $7$ | $10$ | $3$ | Here we stipulate that the top-left cell must contain the number $1$.

A single integer $N$.

If multiple solutions exist, output the arrangement whose sum of the first row and the first column is minimal. Output the board in $N$ lines, each containing $N$ integers separated by single spaces. If no solution exists, output `NO`.

Translated by ChatGPT 5