初衷

這個(gè)學(xué)期開了算法課，要幾個(gè)關(guān)鍵算法思想的代碼實(shí)現(xiàn)。當(dāng)時(shí)感覺學(xué)的還可以了，也做了認(rèn)真的筆記。真正寫代碼的時(shí)候發(fā)現(xiàn)還是

沒有完全掌握。網(wǎng)上關(guān)于這方面的資料也零零散散不是很全，致使走了不少彎路。今晚上實(shí)驗(yàn)成功驗(yàn)收了，感覺自己也收獲不小

遂決定把算法實(shí)現(xiàn)的詳細(xì)思路記錄下來，一是自己坐下總結(jié)、另外也希望給當(dāng)時(shí)想我一樣找資料、搞算法的同學(xué)一些幫助。

這中間我會(huì)盡最大可能的把問題描述清楚。

這篇博文主要寫的是n皇后問題、后續(xù)還會(huì)加上背包問題（動(dòng)態(tài)規(guī)劃和分支界限）、旅行商問題等等。

寫在前面

不管什么問題、都是可以抽象的，對(duì)于任何問題，你總是可以找到幾個(gè)point，它們對(duì)問題全局有著決定性的作用，弄清楚看他們之間的內(nèi)在聯(lián)系；

還有一個(gè)重要的方式就是找特例：對(duì)于一個(gè)無從下手的問題，可以舉幾個(gè)例子，找特例。通過幾個(gè)關(guān)鍵的point和特例，你就能容易的找出隱藏在問

題背后的實(shí)質(zhì)。

在這里我會(huì)給出這個(gè)問題的分析過程、而不會(huì)用成熟的理論來說明問題。如果你只想要代碼的話也可以直接copy。

問題描述：

一個(gè)n*n的棋盤，要在上面放n個(gè)皇后。規(guī)則：兩個(gè)皇后之間如果是同列、同行、同對(duì)角線它們會(huì)互相攻擊。也就是說：棋盤上的任意兩個(gè)皇后皇后

不能為同列、同行、同對(duì)角線。

問題分析

對(duì)于這個(gè)問題、當(dāng)n不大的時(shí)候，可以用窮舉法實(shí)現(xiàn)。對(duì)于n皇后，每一行有n個(gè)位置可以放，一共n行。就會(huì)有n的n次方種情況。對(duì)于這些情況、再一一判斷是不是滿足情況。

其實(shí)一個(gè)關(guān)鍵的點(diǎn)在于：什么時(shí)候判斷已經(jīng)放了皇后的棋盤是否滿足條件，大致可以分為兩種：

1、等棋盤上放了n個(gè)皇后以后判斷

2、放一個(gè)皇后判斷一次、對(duì)于特定的某一次，如果這種情況不滿足條件，那么以這種情況為基礎(chǔ)而生成的情況就不用再判斷了，他們都不會(huì)滿足條件。

比如說：頭兩行有沖突，那么后面的不管怎么放，都沒有意義了，總會(huì)有沖突。

如下圖：

說明：這是四皇后的圖解,樹的每一層對(duì)應(yīng)棋盤的一層，樹的邊上的數(shù)字代表放在棋盤的位置，如：邊上的數(shù)字是3，則代表下一行的皇后位置

是第三行，一次類推。可以看出，第一行有四個(gè)孩子，這是因?yàn)槠灞P上還沒有放任何皇后，所以第一行的每個(gè)位置都可以放而不會(huì)發(fā)生沖突。

第二行就只有三個(gè)孩子因?yàn)檫@個(gè)時(shí)候第一行已經(jīng)有皇后，要保證不和第一樣的發(fā)生沖突，選擇的余地就變小了。一下情況一次類推。

如果考慮全部情況的話，應(yīng)該每個(gè)節(jié)點(diǎn)都有四個(gè)孩子，然后再來判斷最終情況是否滿足情況，這會(huì)坐更多次數(shù)的判斷，導(dǎo)致低效率。

上面兩種判斷法可以導(dǎo)致完全不同的算法效率：

方法一判斷了每一種情況，其實(shí)就是窮舉法。方法二只判斷了一部分情況，對(duì)于那些沒有判斷的情況，是因?yàn)槲覀円呀?jīng)知道他們不可能成為解了，所以就

沒有判斷的必要，可以節(jié)省大量的時(shí)間開支。

（用稍微專業(yè)些的話就是在深度優(yōu)先遍歷解空間的時(shí)候每一步都判斷當(dāng)前狀態(tài)是否滿足條件，如不滿足就沒有就不再繼續(xù)往下遍歷，而是回溯）

所以思路可以是這樣：在第一行放一個(gè)皇后（可以是任意位置），然后在第二行找一個(gè)可行的位置放置，在這個(gè)基礎(chǔ)上在第三行找一個(gè)沒有沖突的位置，如果

發(fā)現(xiàn)某一行沒有地方可放了，那么修改它的上一行，（找到另外一個(gè)沒有沖突的位置），然后在繼續(xù)遍歷。（回溯）

下面得考慮用什么樣的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)結(jié)果：

當(dāng)然，你可以用二維數(shù)組來存放，相當(dāng)于模擬了個(gè)棋盤，有皇后的位置存1，沒有皇后的位置存0，

多數(shù)的做法是用一個(gè)數(shù)組來存放，（一維數(shù)組），下文會(huì)有提到。

算法實(shí)現(xiàn)

有了上面的分析后，再給出算法應(yīng)該就能比較好的理解了

可以用遞歸和非遞歸來求解 ：

非遞歸算法：

NQueens1(int n)
{   int k, n; extern int x[n];  k=0; x[k]=-1;
     while(k>=0)
     {   x[k]=x[k]+1; 
          while((x[k]<n) && (!Place(k)) x[k]=x[k]+1;　　//如果當(dāng)前列不滿足情況，則判斷下一列
          if(x[k]<n)  　　　　　　　　//如果是上文while中的第二個(gè)條件不滿足而退出while循環(huán)，也就是說找到了可以放置的位置
          {   if(k<n-1) {   k=k+1;  x[k]=-1;  }　　　　//判斷當(dāng)前行是不是最后一行，如果是最后一行則表明已經(jīng)找到結(jié)果，打印結(jié)果
              else  printf(x[0:n-1]);     
          }
          else k=k-1;　　　　　　//上文中while因?yàn)榈谝粋€(gè)條件不滿足而退出while循環(huán)，在這行里沒有滿足條件的列，那么退回上一行重新選擇滿足

　　　　　　　　　　　　　　　　　　//條件的的列（回溯）
       }
}

代碼說明：K表示行數(shù)，數(shù)組元素X[K]的值表示第K行的皇后位置，比如X[3]=2,表示第3行皇后的位置是2. 

place()是判斷當(dāng)前位置是否滿足條件的函數(shù)，如果滿足條件返回真，不滿足為假。從循環(huán)可知，如果當(dāng)前位置不可行，則判斷下一列:X[k]=X[k]+1,由于遞歸和非遞歸都會(huì)用到這個(gè)函數(shù)，將在下面提到。

 有人可能注意到X[k]的初始值為-1，是因?yàn)閷?duì)于每一行程序都要從第一個(gè)位置（第一列）判斷，如果不滿足再往后，對(duì)于每一列的處理

是從第一個(gè)while循環(huán)里開始的，里面的X[k]=X[k]+1,使得第一次判斷的是第一列。

遞歸算法：

NQueens2(int k)
{   extern int x[n];  
     x[k]=-1;
     while(1)
     {   x[k]=x[k]+1; 
          while((x[k]<n)&&(!Place(k)) x[k]=x[k]+1;
          if(x[k]<n)    
          {   if(k<n-1) NQueens2(k+1); 　　　　　//如果還沒找到最終解，則遞歸調(diào)用算法，判斷下一行（K+1）
               else printf(x[0:n-1]); 
          }
          else return;
      }
}

對(duì)于兩個(gè)函數(shù)中都用到的place()函數(shù)：

int Place(int k) 
{    int i; extern int x[n];
      for(i=0; i<k-1; i++)
          if( (x[i]==x[k-1]) || (abs(x[i]-x[k-1])==abs(i-k+1)) )
                    return false=0;
      return true=1;
} 

傳入?yún)?shù)是K(行數(shù))，還引入數(shù)組X[n]，這樣就能知道從第一行到第k行的皇后位置，（上文中說說x[k]這個(gè)數(shù)組是存放皇后位置的）

要判斷第k行的x[k]列是否滿足條件，只要用k前的每一行來和它相比較，只要有其中的一行不滿足條件，就返回假。

(x[i]==x[k-1])表示他們?cè)谕涣校?span data-mce-="">(abs(x[i]-x[k-1])==abs(i-k+1)表示他們?cè)谕粚?duì)角線

算法實(shí)現(xiàn)代碼 （遞歸實(shí)現(xiàn)）

#include<fstream>
#include<iostream>

std::ofstream fout("queenoo.txt");

/**//* 記錄當(dāng)前的放置方案 */
int *x; 
/**//* 皇后的個(gè)數(shù)N 和 方案數(shù)目 */
int n,sum=0;
/**//* 檢查參數(shù)所指示的這一行皇后放置方案是否滿足要求 */
int  Place(int);
/**//* 遞歸方法求取皇后放置方案*/
void Queen1(void);
/**//* 用戶遞歸求取皇后放置方案的遞歸方法 */
void TraceBack(int);
/**//* 打印當(dāng)前成功的放置方案 */
void PrintMethod(void);

int main()
{
    using namespace std;
    long start,stop;
    cout<<"input n  輸入皇后個(gè)數(shù) :";
    cin>>n;

    x=(int *)malloc(sizeof(int)*n);
    time(&start);/**//*記錄開始時(shí)間*/
    Queen1();
    time(&stop);/**//*記錄結(jié)束時(shí)間*/
    cout<<"一共的方案數(shù)為："<<sum<<"\n";
    cout<<"共花時(shí)間："<<(int(stop-start))<<"\n";
    fout<< "一共的方案數(shù)為："<<sum<<"\n";
    fout<< cout<<"共花時(shí)間："<<((stop-start))<<"\n";

}

int Place(int r)
{
    int i;
    for(i=0;i<r;i++){
        if(x[r]==x[i] || abs(r-i)==abs(x[r]-x[i]))
            return 0;
    }
    return 1;
}

void TraceBack(int r)
{
    int i;
    if(r>=n){
        PrintMethod();
        sum++;
        /**//* PrintMethod(); */
    }else{
        for(i=0;i<n;i++){
            x[r]=i;
            if(Place(r)) TraceBack(r+1);
        }
    }
}

void PrintMethod(void)
{
    int i,j;
    std::cout<<"第"<<sum<<"個(gè)方案\n";
    fout<<"第"<<sum<<"個(gè)方案\n";
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(j==x[i]) std::cout<<"1",fout<<"1";
            else std::cout<<"0",fout<<"0";
        }
        std::cout<<"\n";
        fout<<"\n";
    }
}

void Queen1(void)
{
    TraceBack(0);
}

以上代碼cfree5編譯通過。

代碼把實(shí)驗(yàn)結(jié)果輸入到文件“queenoo.txt”中，路徑就在編譯器安裝路徑中，和執(zhí)行代碼位于同一目錄。

非遞歸代碼類似，就沒寫出來

后記

解決八皇后問題用到的是一種稱為回溯的方法，在上面的分析過程中就體現(xiàn)了這種思想，在深度優(yōu)先遍歷解空間的時(shí)候加上判斷

條件，只有符合條件的，才繼續(xù)往下遍歷。任何一種理論的產(chǎn)生都是先有實(shí)踐環(huán)節(jié)的，只有在實(shí)踐正確的情況下，才能總結(jié)出理論

而很多算法書都是現(xiàn)給出里論，再給實(shí)例，其實(shí)這不是一種好的學(xué)習(xí)方式，這中間學(xué)習(xí)者少了許多思考、推導(dǎo)的過程，而這過程恰恰

就是理論的雛形，忽視了這個(gè)關(guān)鍵的作用，只是被動(dòng)的的接受算法思想而不知道算法是怎樣產(chǎn)生的，不知其所以然，這樣學(xué)起來自然就

不透徹而且很難掌握。

所以在講皇后問題的時(shí)候，并沒有開篇就講什么是回溯法，回溯法的細(xì)想，如何運(yùn)用回溯法等等。而是用原始的思維去思考解決問題之道，

等接觸回溯法時(shí)才恍然，啊、、這就是回溯法。那時(shí)候?qū)τ诶碚摰膶W(xué)習(xí)就能加深對(duì)算法思想的理解，自己在加以思考分析，就能比較好的

掌握算法。

以上博文如有錯(cuò)誤還望各位神仙大牛指正，在下感激不盡

關(guān)于上文中提到的回溯法，會(huì)在下一篇博文中有詳細(xì)說明，歡迎關(guān)注

如有轉(zhuǎn)載請(qǐng)注明出處：http://www.rzrgm.cn/yanlingyin/

一條魚@博客園 2011-12-19