题目大意：给定一个整数n,将整数1，2，3......n组成一个环，使得相邻两个整数和为素数。

解题思路：DFS，一个一个地放数字，成功放完或者放不完为止。关键是回溯，要把之前放过的数字标记取消掉。从12开始输出量好大，下了我一跳。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath> 
#include<queue> 
using namespace std;
//queue<int> a;                    //本来想开队列保存答案，感觉这样会超时
int arr[21];                     //用来标记是否已经放过改数字 
int cir[21];                    //保存答案 
int num,h,flag,T=1;
void dfs(int n);
int isPrime(int n);

int main()
{
    while(~scanf("%d",&num))
    {
        for(int i=0;i<20;i++) arr[i]=1;
        flag=1;
           cir[1]=1;                //将1先置于环内
        arr[1]=0;                //1已经用过了 
        dfs(2);                 //放第二个数    
        printf("\n");
    }
    return 0;
}

void dfs(int n){
    if(flag)
    {
        printf("Case %d:\n",T);
        flag=0;
        T++;        
    }
    if(n==num+1)
{                //放满了，退出 
   if(isPrime(1+cir[num]))
   {
           for(int i=1;i<num;++i)
        {
            printf("%d ",cir[i]);
        }
         printf("%d\n",cir[num]);
   }      
    return ;
}
int i;
for(i=2;i<=num;i++)            //一遍一遍的扫描下一个要放置的数。
{ 
    if(arr[i]==1 && isPrime(i+cir[n-1]) )//如果这个数没有被放过，并且这个数和之前放进的数相加等于质数，则放进该数。
    {    
        arr[i]=0;            //这个数已经用过 
        h=i;
        cir[n]=i;            //将i这个数放进环里 
        dfs(n+1);            //开始放置下一个数 
        arr[i]=1;            //回溯 
    }
}
if(i==num+1) return ;        //后面的数怎么放都不行了，结束。 
}
int isPrime(int n)                
{
    int i,k;
    k=sqrt(n);
    for(i=2;i<=k;i++)
    {
        if(n%i==0) break;
    }
    if(i<=k) return 0;
    else return 1;
}



样例输入：

6

8

样例输出：

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

​