N皇后问题
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 23888 Accepted Submission(s): 10639
Problem Description
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1
8
5
0
8
5
0
Sample Output
1
92
10
92
10
Author
cgf
Source
入门级搜索N皇后，不打表TLE无疑，最近学了状态压缩模仿着写了下，太神奇了这种操作！
唯一的缺点恐怕就是可读性太差= =但是位运算真的很快，强！
#include<bits/stdc++.h>
using namespace std;
int high,ans;
void dfs(int col,int z1,int z2) //列 主对角线 副对角线
{
if(col==high) {ans++;return;} //列满了说明放满了，方案加一
int can=(high&~(col|z1|z2)); //得到的数二进制中为1得位表示当前可放置(与high是为了防止越界，int只有32位爆了就不好玩了= =，超出棋盘的位置不必考虑)
while(can){ //只要还有可能的位置能放就继续
int cur=(can)&((~can)+1); //得到可放置的位置中最低的一位
can=(can&(~cur)); //将这一位从所有的可能中去除
dfs(col|cur,(z1|cur)>>1,(z2|cur)<<1); //递归,算上这一位后的各个放置情况
}
}
int main()
{
int N,M,i,j,k;
while(scanf("%d",&N)!=EOF&&N){
ans=0;
high=((1<<N)-1);
dfs(0,0,0);
printf("%d\n",ans);
}
return 0;
}
using namespace std;
int high,ans;
void dfs(int col,int z1,int z2) //列 主对角线 副对角线
{
if(col==high) {ans++;return;} //列满了说明放满了，方案加一
int can=(high&~(col|z1|z2)); //得到的数二进制中为1得位表示当前可放置(与high是为了防止越界，int只有32位爆了就不好玩了= =，超出棋盘的位置不必考虑)
while(can){ //只要还有可能的位置能放就继续
int cur=(can)&((~can)+1); //得到可放置的位置中最低的一位
can=(can&(~cur)); //将这一位从所有的可能中去除
dfs(col|cur,(z1|cur)>>1,(z2|cur)<<1); //递归,算上这一位后的各个放置情况
}
}
int main()
{
int N,M,i,j,k;
while(scanf("%d",&N)!=EOF&&N){
ans=0;
high=((1<<N)-1);
dfs(0,0,0);
printf("%d\n",ans);
}
return 0;
}