一道关于数论的奥赛题,大家过来看看啊解决方法

一道关于数论的奥赛题,大家过来看看啊.
应用递归法解决有关数论的问题

在N*N的棋盘上（1 <=N <=10）填入1,2…N*N共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!”

欢迎大家给出自己的思路.

------解决方案--------------------
这题目，我想了半天也没想出搜索之外的办法来。
用个回溯搜索可以把所有解搜索出来，但是数据量惊人。
要“输出第一行、第一列之和均为最小的排列方案”，看来还得在回溯条件上做改动。

/*
将1-N^2这N^2个数添如N*N的方格中，每个方格填一个整数，使所有相邻两个方格内的两个整数之和为质数。
例如N=3时如下，无解。N=4时，2992解？N=5时，917848解？算了半个小时
A0 A1 A2
A3 A4 A5
A6 A7 A8
PRIME(A0+A1)
PRIME(A0+A3)
PRIME(A1+A2)
PRIME(A1+A4)
PRIME(A2+A5)
PRIME(A3+A4)
PRIME(A3+A6)
PRIME(A4+A5)
PRIME(A4+A7)
PRIME(A5+A8)
PRIME(A6+A7)
PRIME(A7+A8)
*/
#include <stdio.h>
#include <math.h>
#include <windows.h>

#define MAX_NUM 30
#define _PRINT_ 0

unsigned long Result[MAX_NUM * MAX_NUM], ResultNum, Used[MAX_NUM * MAX_NUM]={0};
bool PrimeTable[MAX_NUM * MAX_NUM * 2]={ false };
unsigned long N, QN;

/* */
void CreatePrimeTable(void)
{
PrimeTable[0]=false;
PrimeTable[1]=false;
PrimeTable[2]=true;
PrimeTable[3]=true;
for(unsigned long j=5; j <= MAX_NUM * MAX_NUM * 2; j+=2)
{
PrimeTable[j]=true;
for(unsigned long i=3; i <= sqrt((double)j); i+=2)
{
if(j % i == 0)
{
PrimeTable[j]=false;
break;
}
}
}
}

/* */
inline bool IsPrime(unsigned long n)
{
return PrimeTable[n];
}

/* */
bool CheckIt(unsigned long Deep)
{
if(Deep == 0)
{
return true;
}
else if(Deep < N)
{
return IsPrime(Result[Deep] + Result[Deep - 1]);
}
else if(Deep % N == 0)
{
return IsPrime(Result[Deep] + Result[Deep - N]);
}
else
{
return(IsPrime(Result[Deep] + Result[Deep - 1]) && IsPrime(Result[Deep] + Result[Deep - N]));
}
}

/* */
void go(unsigned long Deep)
{
if(Deep == QN)
{
ResultNum++;
#if (_PRINT_)
printf( "Find it! No.%lu\n ", ResultNum);
for(unsigned long i=0; i < QN; i++)
{
printf( "%lu\t ", Result[i]);
if(i % N == N - 1)
{
printf( "\n ");
}
}

#else
printf( "\rFind:%lu ", ResultNum);
#endif
}
else
{
for(unsigned long i=1; i <= QN; ++i)
{
if(!Used[i])
{
Result[Deep]=i;
if(CheckIt(Deep))
{
Used[i]=1;
go(Deep + 1);
Used[i]=0;
}
}
}
}
}

/* */
int main(void)
{
DWORD tim;
ResultNum=0;
printf( "Input N: ");
scanf( "%lu ", &N);
QN=N * N;
tim=GetTickCount();
CreatePrimeTable();
go(0);
printf( "\n\nN=%lu\n ", N);