回溯法解决相邻素数之和问题

Question

数字方阵
时间限制：5000 ms
在NN的棋盘上（1＜N≤10）填入1,2,...NN共N*N个数,使得任意两个相邻的数之和为素数.例如,当N=2时,有 ：
1 2
4 3
其相邻数的和为素数的有:1+2,1+4,4+3,2+3.
当N=4时,一种可以填写的方案如下:
1 2 11 12
16 15 8 5
13 4 9 14
6 7 10 3
在这里我们约定:左上角的格子里必须放数字1.
输入：
一个正整数N
输出：
若有多种解,则需输出第一行之和最小,若第一行和相同,则输出第一列之和最小的排列方案;若无解,则输出"No solution".
第一行为空格分割的两个正整数,分别是该排列方案的第一行、第一列各数字之和.以下n行输出该排列方案,每个数字占4个字符,不足4位的在数字前用空格补齐.
输入样例：
2
输出样例：
3 5
1 2
4 3
直接暴力深搜会爆,虽然时限5秒
有什么办法吗,或者剪枝怎么剪