问题如下：
给定一个正整数n(1<=n<=20), 找出所有满足下列条件的环(按照从小到大顺序输出):
1. 由1...n个元素构成.
2. 任意相邻的两个元素,其相加的和必须是一个素数.

为了使问题简单化,我们不妨设环中的第一个元素总是从1开始.下面给出两个示例:

n = 6
1 4 3 2 5 6
1 6 5 2 3 4

n = 8
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

BTW,顺时针和逆时针算两个不同的结果.

我的方法比较简单:在(n-1)!的搜索空间, 直接搜索,去除一些不可能的分支. 但速度依然不是很快. 不知道有没有更好的方法?

因为这个环是从1开始的, 我们很容易知道这个环必然是奇->偶..... 由于最后一个元素必须要与第一个元素匹配,所以必须是偶数. 那也就意味着n必须是偶数才有解.

嗯嗯，说一下上次我想到的解法：

做一个无向图，图中节点就是 1...n 的数字，然后如果两个数字之和为素数，就在它们之间连一条边。那么上述问题就变成找出这个图中所有长度为 n 的环（也就是哈密尔顿环啦）。解这个问题可以用枚举所有环的办法，也就是找出所有的基本环，然后枚举它们的线性组合。这个是经典问题，资料比较多我就不说了。

这个算法的优势在于利用经典问题的现成算法，应该是比较优的。枚举基本环的线性组合看上去很费时间，但是考虑到我们只需要哈密尔顿环，其实搜索的时候剪枝很容易，应该会比较快。主要问题在于没有利用素数的性质。

利用限制排列生成算法解决这个问题，没有考虑到剔除对称模式，在n<=14时速度还可以。
#include <iostream>
#include <iterator>
#include <windows.h>

using namespace std;

int Prime[]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1,0,0,0,1,
0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,0,0,0};

void f( int n ){
int *a=new int[n+1], *l=new int[n+1], *u=new int[n+1];
int k, p, q;
for( k=0; k<n; ++k ) l[k]=k+1;
l[n]=0;
k=1;
X2: p=0; q=l[0];
X3: a[k]=q;
if( !( k==1 || Prime[a[k-1]+a[k]] ) )
goto X5;
else
if( k==n ){
copy( a+1, a+n+1, ostream_iterator<int>(cout," ") ),cout<<endl;
goto X6;
}
u[k]=p; l[p]=l[q]; ++k; goto X2;
X5: p=q; q=l[p]; if( q!=0 ) goto X3;
X6: --k;
if( k==0 ) return;
p=u[k], q=a[k], l[p]=q;
goto X5;
delete []a; delete []u; delete []l;
}

int main( )
{
int n;
cin>>n;
f( n );
return 0;
}