CV1295N皇后问题

题目描述 Description
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后，任何2个皇后不妨在同一行或同一列或同一斜线上。

输入描述 Input Description
给定棋盘的大小n (n ≤ 13)

输出描述 Output Description
输出整数表示有多少种放置方法。

样例输入 Sample Input
8

样例输出 Sample Output
92

数据范围及提示 Data Size & Hint
n<=13

（时限提高了，不用打表了）

题解

#include<cstdio>
using namespace std;
int n;
bool d[100]={0},b[100]={0},c[100]={0};
int sum=0,a[100];
int search(int i)
{
    int j;
    for (j=1;j<=n;j++)
    if ((!b[j])&&(!c[i+j])&&(!d[i-j+n-1]))
    {
        a[i]=j;
        b[j]=1;
        c[i+j]=1;
        d[i-j+n-1]=1;
        if (i==n) sum++;
        else search(i+1);
        b[j]=0;
        c[i+j]=0;
        d[i-j+n-1]=0;
	}
}
main()
{
	scanf("%d",&n);
    search(1);
    printf("%d",sum);
}