题目描述
Background
This is the first question of the NOIP1997 Senior Group.
P5512 is a data-enhanced version of this problem.
The actual data range for this problem is $1 \le N \le 5$. It is not guaranteed that there exists a non-lookup table approach that can pass the original data range.
Problem Description
On an $N \times N$ ($1 \le N \le 10$) chessboard, fill in the numbers $1, 2, \dots, N^2$ such that the sum of any two adjacent numbers is a prime number.
For example, when $N = 2$, one possible arrangement is:
| $1$ | $2$ |
|---|---|
| $4$ | $3$ |
The sums of adjacent numbers that are prime include:
$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$ |
We stipulate that the top-left corner must be filled with the number $1$.
Input Format
A single number $N$.
Output Format
If there are multiple solutions, output the arrangement where the sum of the first row and the first column is the smallest. If there is no solution, output NO.
Sample Input and Output
Sample Input #1
1
Sample Output #1
NO
Sample Input #2
2
Sample Output #2
1 2
4 3
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分