USACO 1.5.4 Checker Challenge (N皇后问题) 位运算解法

This post is written in Chinese. Please consider using Google Translate

经典的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;
}

Related posts