注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一路

To find the final symmetry & beauty

 
 
 

日志

 
 
 
 

解8皇后问题高效代码,基于bit运算[原创]  

2011-01-27 21:29:59|  分类: 计算之美 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

    N皇后问题大家都熟知的了,不知的话可以google一下,解答和分析一大堆。我在网上找到的最快的代码是基于bit运算的。读了这份代码后深受启发,在代码中加入了自己利用问题对称性解的特征使原代码更加有效率。Bit运算的原理还是搜索剪枝,但是基于bit运算可以直接找到下一枝,可以直接判断重叠等,十分方便和高效。下面是我的代码,我在我的机器上运行16皇后问题用时9秒,我的机器是笔记本core i5,程序为单线程。我在网上没有发现比这个更快的算法了,如果你有兴趣或是有更快的算法,不要忘记告诉我,谢谢。

下面是代码,如果你对阅读代码有问题可以先看一看这一篇文章:

http://www.matrix67.com/blog/archives/266

 

//written by saturnman

//queen_puzzle.cpp

#include<iostream>

#include<vector>

#include<cstdlib>

#include<ctime>

using namespace std;

class Global

{

    public:

        static unsigned int full_pattern;

};

unsigned int Global::full_pattern;

void try_step(unsigned int row_pattern,unsigned int left_diagnal,unsigned int right_diagnal,unsigned int right_edge,int recur_depth,int& count)

{

    //I don't want to make many comments and you should just read the code

    //I tried hard to make the code readable by using meaningful identifiers.

    //Wish you have fun read it :-)

    if(row_pattern!=Global::full_pattern)

    {

        unsigned int avail_position = Global::full_pattern & ~(row_pattern | left_diagnal | right_diagnal | right_edge<<recur_depth | right_edge>>recur_depth);

        while(avail_position!=0x00000000)

        {

            unsigned int right_most_pos = avail_position & -((signed int)avail_position);

            avail_position &= ~right_most_pos;

            try_step(row_pattern | right_most_pos,(left_diagnal | right_most_pos)<<1,(right_diagnal | right_most_pos)>>1,right_edge,recur_depth-1,count);

        }

    }

    else

    {

        ++count;

    }

}

inline int check_valid(int i_index,int j_index,int number)

{

    unsigned int bit_pattern   = 1<<i_index;    //left_edge bit

    unsigned int left_diagonal = bit_pattern;

    unsigned int right_diagnal = bit_pattern;

    unsigned int right_edge    = 1<<j_index;    //right_edge bit

    int count = 0;

    try_step(bit_pattern | right_edge,left_diagonal<<1,right_diagnal>>1,right_edge,number-2,count);

    return count;

}

class sym_triple

{

    public:

        sym_triple()

        {}

        sym_triple(int i_index,int j_index,int degenerate_number)

        {

            this->i_index = i_index;

            this->j_index = j_index;

            this->degenerate_number = degenerate_number;

        }

        int i_index;

        int j_index;

        int degenerate_number;

};

void solve_queen(int number)

{

    Global::full_pattern=0;

    for(int i=0;i<number;++i)

    {

        Global::full_pattern |= 1<<i;

    }

    int result_count=0;

    int init = time(NULL);  //record time when start

    vector<sym_triple> sym_arr;

    //generate pattern

    //make use of symmetry

    //find the left_most and right_most positions that are not conflicted

    //and with this info to make use of symmetry info.

    //As one board has 4 symmetry axes(horizontal mid-line,vertical mid-line,left diagonal and right diagonal line)

    //if one solution was found. we can get eight soloton by transformation. but it is really hard to identify these

    //solutions are different.

    for(int i=0;i<number/2;++i)

    {

        for(int j=i+1;j<number-i;++j)

        {

            if(i==0 && j==number-1)//conflict

            {

                continue;

            }

            else

            {

                if(j==number-1-i)

                {

                    sym_arr.push_back(sym_triple(i,j,2));

                    //flip and rotation make only 2 solution configuration

                }

                else

                {

                    sym_arr.push_back(sym_triple(i,j,4));

                    //flip and rotation make 4 different solution configuration.

                }

            }

        }

    }

    for(vector<sym_triple>::iterator itor = sym_arr.begin();itor!=sym_arr.end();++itor)

    {

        result_count += (itor->degenerate_number)*check_valid(itor->i_index,itor->j_index,number);

    }

    int end = time(NULL);//record time when end

    cout<<"\nUse "<<end-init<<" seconds."<<endl;

    cout<<"result count:"<<result_count<<endl;

}

int main()

{

    while(true)

    {

        cout<<"enter queen"<<endl;

        int number;

        cin>>number;

        if(number>32 || number <3)

        {

            cerr<<"queen number should be less than 32"<<endl;

            exit(1);

        }

        solve_queen(number);

    }

    return 0;

}

 

  评论这张
 
阅读(924)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017