八皇后__位运算优化搜索
题目大意: 和A+B一样经典的八皇后问题，要求输出前三个字典序最小的解，以及总的方案数。
解题思路： 如果N比较小，那么随便搜都可以过。但如果N大等于10，就要求对程序进行优化。
这题我很奇葩地用广搜来做，各种状态压缩压线飘过，搓的一逼。AC后去网上找了几篇解题报告，发现用位运算来优化深搜，非常飘逸。
其中属Matrix67的文章分析地最透彻，最好理解。想深入理解可移步：http://www.matrix67.com/blog/archives/268。
在这里我把集中常用的运算整理下：
去掉最后一位 | (101101->10110) | x >> 1在最后加一个0 | (101101->1011010) | x << 1在最后加一个1 | (101101->1011011) | (x << 1) + 1把最后一位变成1 | (101100->101101) | x | 1把最后一位变成0 | (101101->101100) | (x | 1)-1最后一位取反 | (101101->101100) | x ^ 1把右数第k位变成1 | (101001->101101,k=3) | x | (1 << (k-1))把右数第k位变成0 | (101101->101001,k=3) | x&(~(1 << (k-1))右数第k位取反 | (101001->101101,k=3) | x ^ (1 << (k-1))取末三位 | (1101101->101) | x & 7取末k位 | (1101101->1101,k=5) | x & (1 << (k-1))取右数第k位 | (1101101->1,k=4) | (x >> (k-1)) & 1把末k位变成1 | (101001->101111,k=4) | x | (1 << (k-1))末k位取反 | (101001->100110,k=4) | x ^ (1 << (k-1))把右边连续的1变成0 | (100101111->100100000) | x & (x+1)把右起第一个0变成1 | (100101111->100111111) | x | (x+1)把右边连续的0变成1 | (11011000->11011111) | x | (x-1)取右边连续的1 | (100101111->1111) | (x ^ (x+1)) >> 1去掉右起第一个1的左边 | (100101000->1000) | x & (x ^ (x-1))
测试数据：
13
1 3 5 2 9 12 10 13 4 6 8 11 7
1 3 5 7 9 11 13 2 4 6 8 10 12
1 3 5 7 12 10 13 6 4 2 8 11 9
73712
/*ID:imonlyc1PROG:checkerLANG:C++ */#include <stdio.h>#include <string.h>int state,cnt;int ans[15],n;int GetCol(int a) //不用 log 节省时间{switch (a){case 1:return 1;case 2:return 2;case 4:return 3;case 8:return 4;case 16:return 5;case 32:return 6;case 64:return 7;case 128:return 8;case 256:return 9;case 512:return 10;case 1024:return 11;case 2048:return 12;case 4096:return 13;}}void Dfs(int row, int ld, int rd, int deep) { int pos, col; if (row != state) { pos = state & ~(row | ld | rd); //取合法的位置 while (pos != 0) { col = pos & -pos; //取最右边那一列，col = 1<<x。等于pos&((~pos)+1) pos = pos - col; //慢慢往左移动 if (cnt < 3) ans[deep] = col; //记录前三个的答案，ans[i]表示第i行放的是x列 //三个状态都要做相应改变，对角线一个向左一个向右 Dfs(row + col, (ld + col) >> 1, (rd + col) << 1, deep + 1); } } else { cnt++; if (cnt <= 3) { for (int i = 1; i <= n - 1; i++) printf("%d ",GetCol(ans[i])); printf("%d\n",GetCol(ans[n])); } }}int main(){//freopen("checker.in","r",stdin);//freopen("checker.out","w",stdout);scanf("%d",&n);state = (1 << n) - 1;Dfs(0,0,0,1);printf("%d\n",cnt);return 0;}本文ZeroClock原创，但可以转载，因为我们是兄弟。