在一张N∗N的国际象棋棋盘上，放置N个皇后，使得所有皇后都无法互相直接攻击得到，（皇后可以直接攻击到她所在的横行，竖列，斜方向上的棋子），现在输入一个整数N，表示在N∗N的棋盘上放N个皇后，请输出共有多少种使得所有皇后都无法互相直接攻击得到的方案数。 例如下面这样的摆法，是4皇后的一个解 （1代表有皇后，0代表没有）
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
输入
一个整数N，代表皇后的个数
输出
输出方案数
样例输入1
4
样例输出1
2
样例输入2
8
样例输出2
92
注意一条对角线的行和列的和或者行和列的差是定值
#include <iostream> using namespace std; int n; int count; bool b[200],b1[400],b2[200]; bool in(int x,int y){ return !b[y]&&!b1[x+y]&&!b2[x-y+n]; //b代表列，b1和b2表示对角线 } void dfs(int x){ if(x==n){ count++; //遍历到第n行证明该方法可行 return; } for(int i=0;i<n;i++){ //x行，i列 if(in(x,i)){ //如果x行i列可以放置皇后 b[i]=b1[x+i]=b2[x-i+n]=1; dfs(x+1); //在改点放置皇后，并且到下一行寻找可行皇后放置点放置 b[i]=b1[x+i]=b2[x-i+n]=0; } } } int main(){ cin>>n; dfs(0); //从第零行开始选择 cout<<count; return 0; }
