八皇后图解

元始天尊

    今早学了一下回溯法，其中经典实例是八皇后问题，我没看答案自己做了一下，我不喜欢用命令行的，所以做了更容易说明问题的图形界面。八皇后问题描述为：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.

下面是示例和代码


关键代码：

1. 
   
2. bool place(int* pos,int cur,int layer)
   
3. {
   
4.         for(int i=0;i<layer;i++)
   
5.         {
   
6.                 if(cur == pos[i] || (layer-i == cur-pos[i]) || (layer-i == pos[i]-cur))
   
7.                         return false;
   
8.         }
   
9.         return true;
   
10. }
    
11. 
    
12. void CEightQueenDlg::search(int* pos,int layer)
    
13. {
    
14.         if(layer >= 0 && layer < n)
    
15.         {
    
16.                 for(int i=0;i<n;i++)
    
17.                 {
    
18.                         if(place(pos,i,layer))//如果在位置矩阵中可以在这一层处将皇后放在i位置
    
19.                         {
    
20.                                 pos[layer]=i;
    
21.                                 search(pos,layer+1);
    
22.                         }
    
23.                 }
    
24.         }
    
25. 
    
26.         if(layer == n)
    
27.         {
    
28.                 result.push_back(re(pos));
    
29.         }
    
30. }
    
31. 
    
32. void CEightQueenDlg::queen()
    
33. {
    
34.         int pos[n];
    
35.         for(int i=0;i<n;i++)
    
36.         {
    
37.                 pos[i]=-1;
    
38.         }
    
39. 
    
40.         int layer=0;
    
41.         search(pos,layer);
    
42. 
    
43.         vector<re>::const_iterator itor=result.begin();
    
44.         CString str,temp;
    
45.         int j=0;
    
46.         TRACE("size:%d\n",result.size());
    
47.         while(itor != result.end())
    
48.         {
    
49.                 str="";
    
50. 
    
51.                 for(int i=0;i<n;i++)
    
52.                 {
    
53.                         temp.Format("%d ",(*itor).arr[i]);
    
54.                         str += temp;       
    
55.                 }
    
56.                 m_result.AddString(str);
    
57.                 itor++;
    
58.         }
    
59. }
    

复制代码

项目文件：
EightQueen.rar (39.78 KB, 下载次数: 1)

2014-7-25 18:10 上传

点击文件名下载附件

元始天尊

另：对于实际复杂度的证明，可以通过加入变量来看，我们把步数变量放入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)

非递归搜索：

1. 
   
2. void search(int* pos,int n)
   
3. {
   
4.         int layer=0;
   
5.         while(layer >= 0)
   
6.         {
   
7.                 pos[layer]++;
   
8.                 while(pos[layer]<n && !place(pos,pos[layer],layer))
   
9.                 {
   
10.                         pos[layer]++;
    
11.                 }
    
12. 
    
13.                 if(pos[layer]<n)
    
14.                 {
    
15.                         if(layer == n-1)
    
16.                         {
    
17. /*                                for(int i=0;i<n;i++)
    
18.                                         printf("%d ",pos[i]);
    
19.                                 printf("\n");*/
    
20.                         }
    
21.                         else
    
22.                         {
    
23.                                 layer++;
    
24.                                 pos[layer]=-1;
    
25.                         }
    
26.                 }
    
27.                 else
    
28.                         layer--;
    
29.         }
    
30. }
    

复制代码

1. 
   
2. void search(int* pos,int n)
   
3. {
   
4.         int layer=0;
   
5.         while(layer >= 0)
   
6.         {
   
7.                 while(pos[layer]<n && !place(pos,pos[layer],layer))
   
8.                 {
   
9.                         pos[layer]++;
   
10.                 }
    
11. 
    
12.                 if(pos[layer]<n)
    
13.                 {
    
14.                         if(layer == n-1)
    
15.                         {
    
16.                                 for(int i=0;i<n;i++)
    
17.                                         printf("%d ",pos[i]);
    
18.                                 printf("\n");
    
19.                                 layer--;
    
20.                                 if(layer>=0)
    
21.                                         pos[layer]++;
    
22.                         }
    
23.                         else
    
24.                         {
    
25.                                 layer++;
    
26.                                 pos[layer]=0;
    
27.                         }
    
28.                 }
    
29.                 else
    
30.                 {
    
31.                         layer--;
    
32.                         if(layer>=0)
    
33.                                 pos[layer]++;
    
34.                 }
    
35.         }
    
36. }
    

复制代码