【轉載】USACO 1.5.4 Checker Challenge 位運算解法
2011年9月16日 16:13
本篇文章轉載自我的學長——BYVoid大牛的博客：http://www.byvoid.com/blog/usaco-154-checker/以及http://blog.csdn.net/cmykrgb123/article/details/1854976，轉載請註明出處。
经典的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;
}
