论坛 › 技巧探讨 › 八皇后图解

元始天尊 发表于 2014-7-25 18:09:46

八皇后图解

    今早学了一下回溯法，其中经典实例是八皇后问题，我没看答案自己做了一下，我不喜欢用命令行的，所以做了更容易说明问题的图形界面。八皇后问题描述为：8行8列棋盘，有8个皇后且不能相互攻击，问走法。国际象棋里皇后攻击是处在横竖斜方向。
另外很多人在网上问n皇后回溯算法解法复杂度，在我看来，会比n^n小 把回溯过程看成树型的，每往下一层就多出n种可能，从n种可能中选出非横竖斜方向的，自然要全遍历一次，这样每层都是n次循环。注意n^n >> n! 但是回溯法是有优化效果的，如果发现当前层无法满足，那么下面所有的都不用比较了，第二层如果按照横竖斜方向至少减掉2个分支(处于中间会是3个!)，
处于中间：
        1
1        1        1
处于2边：
1
1        1

每层再至少减掉1分支，这样应该实际复杂度要小于n*(n-2)*(n-2)*(n-3)*(n-4)....*1 这样看，复杂度会比n!小，这是我的理解，不过至少会大于n^3.

下面是示例和代码


关键代码：

bool place(int* pos,int cur,int layer)
{
        for(int i=0;i<layer;i++)
        {
                if(cur == pos || (layer-i == cur-pos) || (layer-i == pos-cur))
                        return false;
        }
        return true;
}

void CEightQueenDlg::search(int* pos,int layer)
{
        if(layer >= 0 && layer < n)
        {
                for(int i=0;i<n;i++)
                {
                        if(place(pos,i,layer))//如果在位置矩阵中可以在这一层处将皇后放在i位置
                        {
                                pos=i;
                                search(pos,layer+1);
                        }
                }
        }

        if(layer == n)
        {
                result.push_back(re(pos));
        }
}

void CEightQueenDlg::queen()
{
        int pos;
        for(int i=0;i<n;i++)
        {
                pos=-1;
        }

        int layer=0;
        search(pos,layer);

        vector<re>::const_iterator itor=result.begin();
        CString str,temp;
        int j=0;
        TRACE("size:%d\n",result.size());
        while(itor != result.end())
        {
                str="";

                for(int i=0;i<n;i++)
                {
                        temp.Format("%d ",(*itor).arr);
                        str += temp;       
                }
                m_result.AddString(str);
                itor++;
        }
}


项目文件：

元始天尊 发表于 2014-7-25 18:37:31

另：对于实际复杂度的证明，可以通过加入变量来看，我们把步数变量放入place的循环中，比较次数可以看做复杂度得到：
n=4        step=84
n=5        step=405
n=6        step=2016
n=7        step=9297
n=8        step=46752
n=9        step=243009
n=10        step=1297558
n=11        step=7416541
n=12        step=45396914
n=13        step=292182579
n=14        step=1995957888

除去84可以看出规律为：1 5 24 110 556 2893   ~   1 5 5^2 5^3 5^4 ...   复杂度要大于 O(5^n)

非递归搜索：

void search(int* pos,int n)
{
        int layer=0;
        while(layer >= 0)
        {
                pos++;
                while(pos<n && !place(pos,pos,layer))
                {
                        pos++;
                }

                if(pos<n)
                {
                        if(layer == n-1)
                        {
/*                                for(int i=0;i<n;i++)
                                        printf("%d ",pos);
                                printf("\n");*/
                        }
                        else
                        {
                                layer++;
                                pos=-1;
                        }
                }
                else
                        layer--;
        }
}



void search(int* pos,int n)
{
        int layer=0;
        while(layer >= 0)
        {
                while(pos<n && !place(pos,pos,layer))
                {
                        pos++;
                }

                if(pos<n)
                {
                        if(layer == n-1)
                        {
                                for(int i=0;i<n;i++)
                                        printf("%d ",pos);
                                printf("\n");
                                layer--;
                                if(layer>=0)
                                        pos++;
                        }
                        else
                        {
                                layer++;
                                pos=0;
                        }
                }
                else
                {
                        layer--;
                        if(layer>=0)
                                pos++;
                }
        }
}

查看完整版本: 八皇后图解