| 站点地图 | 联系我
| www.asm32.net | 2006版 | 资料中心 | linux | asm/asm32 | C/C++ | VC++ | java | 书签 | ASP.Net书签 | 上善若水 厚德载物
 现在位置 :: 主页 >> 资料中心 >> ROOT / CODE / ARITHMETIC /
 

N皇后高效算法

来源(TianyaClub Blog)

From: http://blog.tianya.cn/blogger/post_show.asp?BlogID=252566&PostID=5175652

N皇后高效算法

作者:sunbird69 提交日期:2006-5-9 23:52:00

前些日子看到一篇文章谈论的是N皇后算法的高效,采位的是位运算,其中有些没有看懂。先存入于此,日后好好研究:

/* N Queens Problem */
/* 试探-回溯算法,递归实现 */

/* sum用来记录皇后放置成功的不同布局数;upperlim用来标记所有列都已经放置好了皇后。 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long sum = 0, upperlim = 1,half=0;

/* 试探算法从最右边的列开始。 */
void test(long row, long ld, long rd) {

    if (row != upperlim) {

        /* row,ld,rd进行“或”运算,求得所有可以放置皇后的列,对应位为0, */
        /* 然后再取反后“与”上全1的数,来求得当前所有可以放置皇后的位置,对应列改为1。 */
        /* 也就是求取当前哪些列可以放置皇后。 */
        long pos = upperlim & ~(row | ld | rd);

        while (pos) { /* 0 -- 皇后没有地方可放,回溯。 */
            /* 拷贝pos最右边为1的bit,其余bit置0。 */
            /* 也就是取得可以放皇后的最右边的列。 */
            {
                long p = pos & -pos;

                /* 将pos最右边为1的bit清零。 */
                /* 也就是为获取下一次的最右可用列使用做准备, */
                /* 程序将来会回溯到这个位置继续试探。 */
                pos -= p;

                /* row + p,将当前列置1,表示记录这次皇后放置的列。 */
                /* (ld + p) << 1,标记当前皇后左边相邻的列不允许下一个皇后放置。*/
                /* (ld + p) >> 1,标记当前皇后右边相邻的列不允许下一个皇后放置。*/
                /* 此处的移位操作实际上是记录对角线上的限制,只是因为问题都化归 */
                /* 到一行网格上来解决,所以表示为列的限制就可以了。显然,随着移位 */
                /* 在每次选择列之前进行,原来N×N网格中某个已放置的皇后针对其对角线 */
                /* 上产生的限制都被记录下来了。 */

                if(row==0&&p>half)
                    continue;
                else
                    test(row + p, (ld + p) << 1, (rd + p) >> 1);
            }
        }
    } else {
        /* row的所有位都为1,即找到了一个成功的布局,回溯。 */
        sum++;
    }
}

int main(int argc, char *argv[]) {
    time_t tm;
    int n = 16;

    if (argc != 1)
        n = atoi(argv[1]);
    tm = time(0);

    /* 因为整型数的限制,最大只能32位, */
    /* 如果想处理N大于32的皇后问题,需要 */
    /* 用bitset数据结构进行存储。 */
    if ((n < 1) || (n > 32)) {
        printf(" 只能计算1-32之间\n");
        exit(-1);
    }
    printf("%d 皇后\n", n);

    /* 采用对称式算法计算,增加全局变量half */
    half=(n-1)/2;
    half=upperlim< /* N个皇后只需N位存储,N列中某列有皇后则对应bit置1。 */
    upperlim = (upperlim << n) - 1;

    test(0, 0, 0);
    printf("all %ld counts, ji suan time %d miao \n", sum*2, (int) (time(0) - tm));
    return 0;
    //getch();
}


在我的机器上运行时间是36秒! 很好的算法哦

Link: http://www.asm32.net/article_details.aspx?id=3479


浏览次数 238 发布时间 2008/2/3 15:04:56 从属分类 ARITHMETIC 【评论】【 】【打印】【关闭
 
| www.asm32.net | 2006版 | 资料中心 | linux | asm/asm32 | C/C++ | VC++ | java | 书签 | ASP.Net书签 | 京ICP备09029108号-1