033：Prime RingProblem素环问题

Messj

Problem Description

A ring is composeof n circles as shown in diagram. Put natural number 1, 2, ..., n into eachcircle separately, and the sum of numbers in two adjacent circles should be aprime.
Note: the number of first circle should always be 1.

环是组合成n个圆圈所示的图。把自然数1，2，...，n为进分别各圈，和数字中的两个相邻圈之和应该是一个素数。

注意：第一圈的数量始终应为1。

Input

n (0 < n <20).

Output

The output formatis shown as sample below. Each row represents a series of circle numbers in thering beginning from 1 clockwisely and anticlockwisely. The order of numbersmust satisfy the above requirements. Print solutions in lexicographical order.
You are to write a program that completes above process.
Print a blank line after each case.

输出格式如下图所示的样品。每一行代表一个系列的圆形数字的环从1开始顺时针和按逆时针方向。号的顺序，必须满足上述要求。在字典顺序打印解决方案。

请你写一个程序，完成上述过程。

打印每个案例后，一个空行。

Sample Input

6

8

Sample Output

Case 1:

1 4 3 2 5 6

1 6 5 2 3 4

Case 2:

1 2 3 8 5 6 7 4

1 2 5 8 3 4 7 6

1 4 7 6 5 8 3 2

1 6 7 4 3 8 5 2

Messj

计算规模并不庞大，使用dfs和递归最容易不过

#include<cstdio>
#include<cstring>
#define N 20

using namespace std;
int ans[N];
bool hash[N];
int n;
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41};
bool judge(int x)
{
        for(int i=0;i<13;i++)
                if(prime[i]==x)
                        return true;
        return false;
}
void check()
{
        if(judge(ans[n]+ans[1])==false)
                return ;
        for(int i=1;i<=n;i++)
        {
                if(i!=1)
                        printf(" ");
                printf("%d",ans[i]);
        }        
        printf("\n");
}
void DFS(int num)
{
        if(num>1)
                if(judge(ans[num]+ans[num-1])==false)
                        return ;
        if(num==n)
        {
                check();
                return ;
        }
        for(int i=2;i<=n;i++)
        {
                if(hash[i]==false)
                {
                        hash[i]=true;
                        ans[num+1]=i;
                        DFS(num+1);
                        hash[i]=false;     //关键！！！回溯！！！ 
                }
        }
        
}
int main()
{
        int cas=0;
        while(scanf("%d",&n)!=EOF)
        {
                cas++;
                for(int i=0;i<N;i++)
                        hash[i]=false;
                ans[1]=1;
                printf("Case %d:\n",cas);
                hash[1]=true;
                DFS(1);
                printf("\n");
        }
        return 0;
}