N皇后问题

在N*N的方格棋盘搁置了N个皇后，使得它们不互相攻打（即任意2个皇后不容许处在同一排，同一列，也不容许处在与棋盘边框成45角的斜线上。
你的工作是，对于给定的N，求出有多少种非法的搁置办法。

Input
共有若干行，每行一个正整数N≤10，示意棋盘和皇后的数量；如果N=0，示意完结。
Output
共有若干行，每行一个正整数，示意对应输出行的皇后的不同搁置数量。
Sample Input
1
8
5
0
Sample Output
1
92
10

这道题我老是Time Limit,有空还要优化一下，有大佬请帮我看下

////求N*N的格子摆放皇后的摆法（求有几种摆法而不是能够放多少个皇后）（递归） //#include<iostream>//#include<algorithm>//#include<string>//#include<string.h>//#include<cstdio>//#include<queue>//#include<stack> //#include<set> //using namespace std;//int n,cnt;//int vis[3][50];//vis[3]第一个中括号来辨别不同拜访类型三种类型，0(vis[0][])示意判断 同一列 的格子是否被拜访过////1(vis[1][])示意判断 右斜对角 的格子是否被拜访过，2(vis[2][])示意判断 左斜对角 的格子是否被拜访过////#include<bits/stdc++.h>//万能头文件//void dfs(int row){//把queen所在的行传入dfs //    if(row == n + 1 ){//递归进口条件、边界(如果超过第n行了) //        cnt++;//递归终止回溯一次，记录一次个数 //        return ; //    }//    for(int i = 1; i <= n; i++){//        if(vis[0][i] == 0 && vis[1][n + row - i] == 0 && vis[2][i + row] == 0){//            vis[0][i] = vis[1][n + row - i] = vis[2][i + row] = 1;//            dfs(row + 1);//            vis[0][i] = vis[1][n + row - i] = vis[2][i + row] = 0;//在深搜遍历的时候每一个格子的同行同列、左右对角都被拜访标记了//            //然而回溯的时候只是找到了一个适合的格子，（除该以后格子外）其余格子要从新复原为未拜访 //        }//    }//}//int main(){//    memset(vis,0,sizeof(vis));//    while(cin >> n,n != 0){////    int cnt = 0;//记录皇后搁置的数量,应定义为全局变量  ////    int n;//因为深搜外面也用到该变量，应定义为全局变量//        cnt = 0; //        dfs(1); //        cout << cnt << endl;//    }//    return 0;//}//

另一种办法，引入check函数，但实质还是递归

////求N*N的格子摆放皇后的摆法（求有几种摆法而不是能够放多少个皇后）（递归） //#include<iostream>//#include<algorithm>//#include<string>//#include<string.h>//#include<cstdio>//#include<queue>//#include<stack> //#include<set> //using namespace std;//int n,cnt;//int a[10];//a[i]示意第i行上的queen放于a[i]列上，如a[3] = 7示意第3行第7列的格子有queen ////#include<bits/stdc++.h>//万能头文件 ////字符翻转 //bool check(int x, int y){//传入行值和列值(相当于a[i]),看是否和queen所在的值绝对应或同行同列斜对角 //    for(int i = 1; i <= x; i++){//只用看在某行格子放queen之后，其前x行所对应的格子满足不满足条件,一个一个格子枚举比照 //        if(a[i] == y){//check同列是否满足，应为是按行放，每行只放一个，同行无需验证 //            return false;//判断a[i]的值是否等于1,2,3,4,5,6等dfs外面for(的i值)，排除同列的//            //不满足这个if及上面两个if就算找到了，完结check进行赋值操作a[row] = i //        }//        if(i + a[i] == x + y){//check / 对角线是否满足 //            return false;//        }//        if(i - a[i] == x - y){//check \ 对角线是否满足 //            return false;//        }    //    }//    return true;//留神要放在for循环里面，for全副执行之后没问题再返回true.都没有问题，返回queen能够放在这个格子 //} //void dfs(int row){//把queen所在的行传入dfs //    if(row == n + 1 ){//递归进口条件、边界(如果超过第n行了) //        cnt++;//递归终止回溯一次，记录一次个数 //        return ; //    }//    for(int i = 1; i <= n; i++){//        if(check(row,i)){//check一下第row行的皇后能不能放在第row行第i列上//            a[row] = i; //能够放就给第row行的第i个(列)格子放上 //            dfs(row + 1);//            a[row] = 0;//进行完每次回溯把相应的第row行还原置零，从新开始，即没次dfs完后row行的皇后地位回到第一列开始往后找 //        }      //    }//}//int main(){//    while(cin >> n,n != 0){////    int cnt = 0;//记录皇后搁置的数量,应定义为全局变量  ////    int n;//因为深搜外面也用到该变量，应定义为全局变量//        cnt = 0; //        dfs(1); //        cout << cnt << endl;//    }//    return 0;//}//

Prime Ring Problem

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Input
n (0 < n < 20).
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must 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.
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

#include<iostream>#include<algorithm>#include<string>#include<string.h>#include<cstdio>#include<queue>#include<stack> #include<set> using namespace std;/*素数环指的是将从1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，后果均为素数*/ int n,a[30],vis[30];//n是数字的个数，a[i]是需遍历的数组，vis[]是标记数组是否被拜访过 bool Prime(int yy)//判断素数{    for(int i=2; i<=sqrt(yy); i++)    {        if(yy%i==0)        {            return false;        }    }    return true;}void dfs(int t){//此处的t只是传参，跟main函数外面的t没有关系     if(t == n && Prime(a[t - 1] + a[0])){//t是从0开始，当t=n时阐明a[0,...t - 1]都填入了合规的数         for(int i = 0; i < t - 1; i++){//num从0开始             printf("%d ",a[i]);        }        printf("%d\n",a[t - 1]);//a[num - 1]就是传入的num下标对应的值     }else{//尝试能够填入a[i]的每一种可能性(穷举)         for(int i = 2; i <= n; i++){//i代表所有的可能性             if(vis[i] == 0 && Prime(i + a[t - 1])){//i没有应用过，还没连贯在环上并且i和他前一位的和是素数                 //此处i = 2是因为，dfs(1)从1开始并且 1 = a[1-1],所以从2 开始枚举(看2与1之和是否素数以及)                vis[i] = 1;//用过的数标记1                a[t] = i; //满足条件给所求数组的第一个地位a[1]赋值                dfs(t + 1);//在a[1] = i根底上 对i之后的每个数持续递归判断                vis[i] = 0;//进行完每次通过n此dfs后,该回溯的时候把相应的i还原置零，不便下一个传入的t持续枚举             }        }    } } int main(){    int t = 1;//定义一个用来记录case后序号的变动     a[0] = 1;    while(cin >> n){        memset(vis,0,sizeof(vis));//标记数组vis初始化为0        printf("Case %d:\n",t++);//输入一下头部格局,case前面的数字自增         dfs(1);//传入1开始进行深搜         printf("\n");    }}