小航走入赛场，比赛即将开始……
主持人：欢迎来到深度搜索基础训练的比赛现场。首先，感谢全心全意为我们挖坑、绞尽脑汁出难题的出题老师们；然后，感谢古灵精怪的农夫John；最后，感谢c++……废话少说，比赛开始！
小航看向第一题……
【搜索与回溯算法】N皇后问题
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述：
在一个nXn的国际象棋棋盘上放置n(n<=12)个皇后，使它们不能互相攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。试求出所有方法。
输入：
输入一个数n .(n<=12)
输出：
输出所有的排列方案总数。
样例输入：
4
样例输出：
2
“思路是
：循环行，一列一列地试……”小航想道。接着，写下了代码。
#include<iostream>
using namespace std;
int a[105],b[105],c[105],n,s;//数组a为判断列是否放置皇后，b、c都是判断对角线是否放置皇后
void dg(int x)//循环行
{
for(int i=1;i<=n;i++)//循环列
{
if(a[i]!=1&&b[x+i]!=1&&c[i-x+n-1]!=1)
{
a[i]=1;
b[i+x]=1;
c[i-x+n-1]=1;//上面两步及这步都是标记
if(x==n)
{
s++;//当放到最后一个，方案数增加
}
else
{
dg(x+1);//进入下一行放置
}
a[i]=0;
b[i+x]=0;
c[i-x+n-1]=0;//回溯
}
}
}
int main()
{
cin>>n;
dg(1);
cout<<s;//输出方案数
}
小航很快就把第一道题做完了，准备迎接下一题……
