Source
Description
在N*N的方格棋盤放置了N個皇后，使得它們不相互攻擊（即任意2個皇后不允許處在同一排僻族，同一列磷脯，也不允許處在與棋盤邊框成45角的斜線上。
你的任務(wù)是烤黍，對于給定的N，求出有多少種合法的放置方法傻盟。
Input
共有若干行速蕊，每行一個正整數(shù)N≤10，表示棋盤和皇后的數(shù)量娘赴；如果N=0规哲，表示結(jié)束。
Output
共有若干行诽表，每行一個正整數(shù)唉锌，表示對應(yīng)輸入行的皇后的不同放置數(shù)量。
Sample Input
1
8
5
0
Sample Output
1
92
10
因?yàn)镹皇后不可以放在同一行竿奏，所以可以用一維數(shù)組來表示袄简，比如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個皇后的位置已經(jīng)放好，所以種數(shù)加一平痰；
{
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);
}
}
}
還有某個大神用位運(yùn)算實(shí)現(xiàn)的，看不懂宗雇，先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);
}
}
}
相關(guān)的題：http://www.scut.edu.cn/oj/ 題號：2513
Description
八皇后問題是一個以國際象棋為背景的問題：如何能夠在 8×8 的國際象棋棋盤上放置八個皇后昂芜，使得任何一個皇后都無法直接吃掉其他的皇后。
為了達(dá)到此目的赔蒲，任兩個皇后都不能處于同一條橫行泌神、縱行或斜線上良漱。八皇后問題可以推廣為更一般的 n皇后擺放問題：這時棋盤的大小變?yōu)?n×n，而皇后個數(shù)也變成n欢际。
考慮到網(wǎng)上遍布八皇后的標(biāo)準(zhǔn)程序母市，這里另外做個限制，要求第一行第一列上必須有皇后
Input
一個數(shù)n损趋，表示棋盤大小為n*n患久，有n個皇后。
Output
只有一個數(shù)字浑槽，為解的個數(shù)蒋失。當(dāng)沒有解時輸出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);
}
