经典八皇后问题，要求输出所有解的数目。对照版为以前写的加了多个优化的非位运算版。
　　效果还是很明显的，下图是在我机器上的评测结果，左侧为位运算版，右侧是对照版。数据规模从上到下是8~17。
l200711318283.gif

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/*
  八皇后位运算实现 By WindyWinter.
  感谢Matrix67的启发
*/
#include <fstream>
using namespace std;
 
ifstream infile("8queens.in",ifstream::in);
ofstream outfile("8queens.out",ofstream::out);
unsigned tot=0,high;
 
void dfs(unsigned list,unsigned lc,unsigned rc)  //1表示允许放皇后
{
  if (list==0) tot++;
  else
  {
    unsigned t=list & lc & rc,p;
    while (t>0)
    {
      p=~(t & -t);  //取出最右边一个可以放皇后的位置,将其取反,准备将这一位从允许位置中除去以继续搜索下一行
      dfs(list & p,(lc & p)>>1 | high,(rc & p)<<1 | 1);  //"| high"在lc最左边补1,"| 1"在rc最右边补1
      t&=p;
    }
  }
}
 
int main()
{
  int n,l;
  infile>>n;
  high=1<< n-1;
  for (int i=0;i<(n>>1);i++)  //第一行的皇后限定位置在中间至最右边
  {
    l=~(1<<i) & ((1<<n)-1);
    dfs(l,l>>1 | high,l<<1 | 1);
  }
  tot=tot<<1;
  if (n & 1)  //如果n为奇数,单独搜索第一行皇后在最中间一列的情况
  {
    l=~(1<<(n>>1)) & ((1<<n)-1);
    dfs(l,l>>1 | high,l<<1 | 1);
  }
  outfile<<tot<<endl;
  infile.close(); outfile.close();
  return 0;
}