学步园

/*
    搜素与回溯算法:
                搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，
            可以利用搜索与回溯的技术求解。回溯是搜索算法中的一种控制策略。
            它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，
            一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，
            直至得到解或证明无解。
                如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进,如果碰到死胡同，
            说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，
            如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，
            再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。
            按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。


********************************************

递归回溯法算法框架[一]
int Search(int k)//当然，这里不仅仅局限于一个变量
　{
　for (i=1;i<=算符种数;i++)
　　if (满足条件)
　　   {
　　　　保存结果
　　　　if (到目的地) 输出解;
　　　           else Search(k+1);
　　　　恢复：保存结果之前的状态{回溯一步}
　 　  }
　}

递归回溯法算法框架[二]
int Search(int k)
　{
　  if  (到目的地) 输出解;
　　　else
　　　　for (i=1;i<=算符种数;i++)
　　　　　if  (满足条件)
　　　　　　　{
　　　　　　　　保存结果;
　　　                  Search(k+1);
　　　　　　　　恢复：保存结果之前的状态{回溯一步}
　　　　　　　}
　}



***********************************************


*/

# include<cstdio>
# include<iostream>
# include<cstring>

using namespace std;

int a[21];
int vis[21];
int ans = 0;
int hash[30];

int is_prime( int x,int y )
{
    memset(hash,0,sizeof(hash));
    int l = x+y;
    hash[0] = 1;
    hash[1] = 1;
    for ( int i = 2;i < 30;i++ )
        {
            if (!hash)
                {
                    for ( int j = i*i;j < 30;j+=i )
                        {
                            hash[j] = 1;
                        }
                }
        }

    if ( hash[l] )
        return 0;
        else
            return 1;
}


int print()
{
    ans++;
    cout<<"<"<<ans<<">";
    for ( int j = 1;j <= 20;j++ )
        cout<<a[j]<<" ";
    cout<<endl;
}


int search( int t )
{
    for ( int i = 1;i <= 20;i++ )
        {
            if ( is_prime(a[t-1],i)&&(!vis[i]))
                {
                    a[t] = i;
                    vis[i] = 1;
                    if ( t==20 )
                        {
                            if ( is_prime(a[20],a[1]))
                                print();
                        }
                        else
                            search(t+1);
                            vis[i] = 0;
                }
        }
}



int main(void)
{
    memset(a,0,sizeof(a));
    memset(vis,0,sizeof(vis));
    search(1);
    cout<<ans<<endl;

    return 0;
}