四阶素数幻方问题

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

(原帖见:http://topic.csdn.net/u/20070830/18/1f1957c1-5e66-4c3b-8883-d7eef64c8da1.html)

NowCan 网友的解法:

直接递归搜，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;
}

几乎未加任何处理,转成VB代码如下:

Dim prime() As Byte, result() As Long, used() As Byte, n As Long, resultcount As Long
Function checkit(ByVal level As Long) As Byte
If level = 0 Then checkit = 1: Exit Function
If level < n Then checkit = prime(result(level) + result(level - 1)): Exit Function
If level Mod n = 0 Then checkit = prime(result(level) + result(level - n)): Exit Function
checkit = prime(result(level) + result(level - 1)) * prime(result(level) + result(level - n))
End Function

Sub run(Optional ByVal level As Long = 0)
Dim i As Long, j As Long
If level = n * n Then
resultcount = resultcount + 1
Debug.Print "No." & resultcount & vbCrLf & String(4 * n, "-")

For i = 0 To n - 1
For j = 0 To n - 1
Debug.Print Left(result(i * n + j) & "   ", 4);
Next
Debug.Print
Debug.Print
Next
Else
For i = 1 To n * n
If used(i) = 0 Then
result(level) = i
If checkit(level) = 1 Then
used(i) = 1
run level + 1
used(i) = 0
End If
End If
Next
End If
Close #1
End Sub

Sub main()
Dim i As Long, tt As Double
n = 4
ReDim prime(n * n * 2)
ReDim result(n * n)
ReDim used(n * n)
ReDim s(1 To 1000000)
prime(2) = 1
prime(3) = 1
For i = 5 To 2 * n * n Step 2
For j = 3 To Int(Sqr(i))
If i Mod j = 0 Then Exit For
Next
If j = Int(Sqr(i)) + 1 Then prime(i) = 1
Next
tt = Timer
run
MsgBox "共找到" & resultcount & "组解，用时" & Timer - tt & "秒钟!"
End Sub 

返回:

No.1
----------------
1   2   11  12 

4   9   8   5  

7   10  3   14 

6   13  16  15 

No.2
----------------
1   2   11  12 

4   9   8   5  

13  10  3   14 

6   7   16  15 

No.3
----------------
1   2   11  12 

4   15  8   5  

7   16  3   14 

6   13  10  9  

No.4
----------------
1   2   11  12 

4   15  8   5  

13  16  3   14 

6   7   10  9  

No.5
----------------
1   2   11  12 

10  3   8   5  

7   16  15  14 

6   13  4   9  

No.6
----------------
1   2   11  12 

10  3   8   5  

13  16  15  14 

6   7   4   9  

No.7
----------------
1   2   11  12 

10  9   8   5  

7   4   3   14 

6   13  16  15 

No.8
----------------
1   2   11  12 

10  9   8   5  

7   4   15  14 

6   13  16  3  

No.9
----------------
1   2   11  12 

10  9   8   5  

13  4   3   14 

6   7   16  15 

No.10
----------------
1   2   11  12 

10  9   8   5  

13  4   15  14 

6   7   16  3  

No.11
----------------
1   2   11  12 

16  3   8   5  

7   10  9   14 

6   13  4   15 

No.12
----------------
1   2   11  12 

16  3   8   5  

13  10  9   14 

6   7   4   15 

No.13
----------------
1   2   11  12 

16  15  8   5  

7   4   3   14 

6   13  10  9  

No.14
----------------
1   2   11  12 

16  15  8   5  

7   4   9   14 

6   13  10  3  

No.15
----------------
1   2   11  12 

16  15  8   5  

13  4   3   14 

6   7   10  9  

No.16
----------------
1   2   11  12 

16  15  8   5  

13  4   9   14 

6   7   10  3  

.......

共计2992组解法