问一个四阶素数幻方问题
看了有趣的算法这本书,里面有这个问题.想了颇久,想不出什么算法来,希望高手指点指点,谢谢!!

用1到16构成一个四阶幻方,要求任意相邻两个方格中的数字之各均为素数?


[解决办法]
也就是从（1，1）开始在每个格子中枚举可填写的所有数
[解决办法]
1+21+41+61+101+121+16
2+12+32+52+92+112+15
3+23+43+83+103+143+16
4+14+34+74+94+134+15
5+25+65+85+125+14
6+16+56+76+116+13
7+47+67+107+127+16
8+38+58+98+118+15
9+29+49+89+109+14
10+110+310+710+910+13
11+211+611+811+12
12+112+512+712+11
13+413+613+1013+16
14+314+514+914+15
15+215+415+815+1415+16
16+116+316+716+1316+15

[解决办法]
直接递归搜，4阶很快的。以下这个程序就是这样的思路，结果未经过验证。

/*
将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);
printf("Total=%lu\n", ResultNum);

printf("Time=%lu\n", GetTickCount() - tim);
return 0;
}