问一个四阶素数幻方问题

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

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

9 个解决方案

#1

打错字啦.是相邻两个方格中的数字之和均为素数.

#2

不只一个方案吧，用搜索搜就是了。
如果要找出所有的方案，那搜索就不太现实了。。

#3

ls的也太抽象了吧...可否具体一点...

#4

也就是从（1，1）开始在每个格子中枚举可填写的所有数

#5

1+2 1+4 1+6 1+10 1+12 1+16
2+1 2+3 2+5 2+9 2+11 2+15
3+2 3+4 3+8 3+10 3+14 3+16
4+1 4+3 4+7 4+9 4+13 4+15
5+2 5+6 5+8 5+12 5+14
6+1 6+5 6+7 6+11 6+13
7+4 7+6 7+10 7+12 7+16
8+3 8+5 8+9 8+11 8+15
9+2 9+4 9+8 9+10 9+14
10+1 10+3 10+7 10+9 10+13
11+2 11+6 11+8 11+12
12+1 12+5 12+7 12+11
13+4 13+6 13+10 13+16
14+3 14+5 14+9 14+15
15+2 15+4 15+8 15+14 15+16
16+1 16+3 16+7 16+13 16+15

#6

左上角1-16,根据相邻格的可能值递归

#7

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

#8

应该可以优化吧，一种方案旋转就成了四种方案了，
而且填入一个数后只需要对他的上方及左方验证。

#9

结.谢了.

#1