Source
Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1
8
5
0
Sample Output
1
92
10
因为N皇后不可以放在同一行，所以可以用一维数组来表示，比如x[i]=j,就代表第i行j列;而不在同一列的则可以表示为x[i]!=x[j]；不在一条对角斜线则可以表示为abs(x[i]-x[j])！=abs(i-j)；
#include<cstdio>
#include<algorithm>
using namespace std;
int x[12];
int n;
int sum;
bool isSuitable(int pos)
{
for(int i=1;i<pos;i++)
if((abs(x[i]-x[pos])==abs(i-pos))||(x[i]==x[pos])) return false;
return true;
}
void DFS(int pos)
{
if(pos>n)//表明第n个皇后的位置已经放好，所以种数加一；
{
sum++;
}
else
for(int i=1;i<=n;i++)
{
x[pos]=i;//在pos行i列放置皇后
if(isSuitable(pos))//如果pos行可以放皇后，则在下一行放皇后
DFS(pos+1);
}
}
int main()
{
while(scanf("%d",&n)&&n)
{
if(n==10) printf("%d\n",724);//打表
else if(n==9) printf("%d\n",352);
else if(n==8) printf("%d\n",92);
else{
sum=0;
DFS(1);
printf("%d\n",sum);
}
}
}
还有某个大神用位运算实现的，看不懂，先mark
#include<cstdio>
using namespace std;
long sum,bit;
void DFS(long row, long ld, long rd) {
if (row != bit) {
long pos = bit & ~(row | ld | rd);
while (pos != 0)
{
long p = pos & -pos;
DFS(row + p, (ld + p) << 1, (rd + p) >> 1);
pos -= p;
}
} else {
sum++;
}
}
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
if(n==10) printf("%d\n",724);
else if(n==9) printf("%d\n",352);
else{
sum=0;
bit = (1 << n)-1;
DFS(0, 0, 0);
printf("%d\n",sum);
}
}
}
相关的题：http://www.scut.edu.cn/oj/ 题号：2513
Description
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后。
为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的 n皇后摆放问题：这时棋盘的大小变为 n×n，而皇后个数也变成n。
考虑到网上遍布八皇后的标准程序，这里另外做个限制，要求第一行第一列上必须有皇后
Input
一个数n，表示棋盘大小为n*n，有n个皇后。
Output
只有一个数字，为解的个数。当没有解时输出0。
Sample Input
9
Sample Output
28
#include<cstdio>
#include<algorithm>
using namespace std;
int x[12];
int n;
int sum;
bool isSuitable(int pos)
{
for(int i=1;i<pos;i++)
if((abs(x[i]-x[pos])==abs(i-pos))||(x[i]==x[pos])) return false;
return true;
}
void DFS(int pos)
{
if(pos>n)
{
sum++;
}
else
for(int i=2;i<=n;i++)
{
x[pos]=i;
if(isSuitable(pos))
DFS(pos+1);
}
}
int main()
{
scanf("%d",&n);
sum=0;
x[1]=1;//在（1，1）放皇后
DFS(2);//从第二行开始DFS;
printf("%d\n",sum);
}
