USACO 1.5.4 Checker Challenge （N皇后问题） 位运算解法
经典的N皇后（8皇后扩展）问题，学过算法的都知道。
这道题要用回溯法，搜索+优化，但一般的方法很难解决N>=13以上的问题。所以这里重点介绍位操作法。
什么是位运算？ 程 序 中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。比如，and运算本来是一个逻辑运 算 符，但整数与整数之间也可以进行and运算。举个例子，6的二进制是110，11的二进制是1011，那么6 and 11的结果就是2，它是二进制 对应位进行逻辑运算的结果（0表示False，1表示True，空位都当0处理）： 110 AND 1011
0010 –> 2 由于位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。
我的解法基本思想还是用回溯法，和普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在 纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。我们以6x6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经 标在左图上了。红色、蓝色和绿色的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。
upperlim=(1 << n)-1意为算出该棋盘的目标状态（全部被占满）。
pos=upperlim & ~(row | ld | rd)
把它们三个并起来，得到该行所有的禁位，取反后就得到所有可以放的位置（用pos来表示）。
p=pos & -pos;
-a相当于~a + 1，这里的代码就相当于pos & (~pos+1)，其结果是取出最右边的那个1。
这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。
注意递归调用时三个参数的变化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。
最后，如果递归到某个时候发现row=upperlim (目标状态111111) 了，说明六个皇后全放进去了，此时程序找到的解的个数加1。
代码如下：
/*
ID: cmykrgb1
PROG: checker
LANG: C++
*/
#include <stdio.h>
FILE *fi,*fo;
unsigned long int upperlim,sum;
int a[14],n;
int ps(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 test(unsigned long int row,unsigned long int ld,unsigned long int rd,int deep)
{
unsigned long int pos,p;
if (row!=upperlim)
{
pos=upperlim & ~(row | ld | rd);
while (pos!=0)
{
p=pos & -pos;
pos=pos-p;
if (sum<3) a[deep]=p;
test(row+p,(ld+p)<< 1,(rd+p)>> 1,deep+1);
}
}
else
{
sum++;
int i;
if (sum<=3)
{
for (i=1;i<=n-1;i++)
fprintf(fo,"%d ",ps(a[i]));
fprintf(fo,"%dn",ps(a[n]));
}
}
}
int main(void)
{
fi=fopen("checker.in","r");
fo=fopen("checker.out","w");
fscanf(fi,"%d",&n);
fclose(fi);
upperlim=(1 << n)-1;
test(0,0,0,1);
fprintf(fo,"%dn",sum);
fclose(fo);
return 0;
}
上次修改时间 2017-05-26