資料結構課程設計回溯法解決8皇后n皇后問題

資料結構課程設計

學院：資訊科學技術學院

專業：電子資訊工程（1）

姓名：謝後樂

學號： 20101601310015

n皇后問題

n皇后問題：

在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照西洋棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n後問題等價於再n×n的棋盤上放置n個皇后，任何2個皇后不妨在同一行或同一列或同一斜線上。

回溯法簡介：

回溯法(探索與回溯法)是一種選優搜尋法，按選優條件向前搜尋，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。

我們發現，對於許多問題，所給定的約束集d具有完備性，即i元祖（x1，x2，…，xi）滿足d中僅涉及到x1，x2，…，xi的所有約束意味著j（j<=i）元組（x1，x2，…）一定也滿足d中僅涉及到x1，x2，…，的所有約束，i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得（x1，x2，…，）違反d中僅涉及到x1，x2，…，的約束之一，則以（x1，x2，…，）為字首的任何n元組（x1，x2，…， j+1，…，）一定也違反d中僅涉及到x1，x2，…，xi的乙個約束，n≥i≥j。因此，對於約束集d具有完備性的問題p，一旦檢測斷定某個j元組（x1，x2，…）違反d中僅涉及x1，x2，…，的乙個約束，就可以肯定，以（x1，x2，…）為字首的任何n元組（x1，x2，…，）都不會是問題p的解，因而就不必去搜尋它們、檢測它們。

回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比列舉法效率更高的演算法。

空間樹　　回溯法首先將問題p的n元組的狀態空間e表示成一棵高為n的帶權有序樹t，把在e中求問題p的所有解轉化為在t中搜尋問題p的所有解。樹t類似於檢索樹，它可以這樣構造：　　設si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|si| =mi，i=1，2，…，n。

從根開始，讓t的第i層的每乙個結點都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。照這種構造方式，e中的乙個n元組（x1，x2，…）對應於t中的乙個葉子節點，t的根到這個葉子結點的路徑上依次的n條邊的權分別為x1，x2，…，，反之亦然。

另外，對於任意的0≤i≤n-1，e中n元組（x1，x2，…）的乙個字首i元組（x1，x2，…，xi）對應於t中的乙個非葉子節點，t的根到這個非葉子結點的路徑上依次的i條邊的權分別為x1，x2，…，xi，反之亦然。特別，e中的任意乙個n元組的空前綴（），對應於t的根。　　因而，在e中尋找問題p的乙個解等價於在t中搜尋乙個葉子節點，要求從t的根到該葉子結點的路徑上依次的n條邊相應帶的n個權x1，x2，…滿足約束集d的全部約束。

在t中搜尋所要求的葉子節點，很自然的一種方式是從根出發，按深度優先的逐步深入，即依次搜尋滿足約束條件的字首1元組（x1i）、字首2元組（x1，x2）、…，字首i元組（x1，x2，…，xi），…，直到i=n為止。　　在回溯法中，上述引入的樹被稱為問題p的狀態空間樹；樹t上任意乙個結點被稱為問題p的狀態結點；樹t上的任意乙個葉子節點被稱為問題p的乙個解狀態結點；樹t上滿足約束集d的全部約束的任意乙個葉子結點被稱為問題p的乙個回答狀態結點，它對應於問題p的乙個解

解題思路：

要解決n皇后問題，其實就是要解決好怎麼放置這n個皇后，每乙個皇后與前面的所有皇后不能在同一行、同一列、同一對角線，在這裡我們可以以行優先，就是說皇后的行號按順序遞增，只考慮第i個皇后放置在第i行的哪一列，所以在放置第i個皇后的時候，可以從第1列判斷起，如果可以放置在第1個位置，則跳到下一行放置下乙個皇后。如果不能，則跳到下一列...直到最後一列，如果最後一列也不能放置，則說明此時放置方法出錯，則回到上乙個皇后向之前放置的下一列重新放置。

此即是回溯法的精髓所在。當第n個皇后放置成功後，即得到乙個可行解，此時再回到上乙個皇后重新放置尋找下乙個可行解...如此後，即可找出乙個n皇后問題的所有可行解。

在解決n皇后之前，我們不妨先來看看乙個比較簡單的例子，也就是8皇后問題，8皇后也就是n皇后問題中的一種特殊情況，我們只要把8皇后問題解決了，n皇后問題自然也迎刃而解。根據上面解題思路我們寫出8皇后的源程式。

#include<>

#define a 8

int icount=0;

int x;

int site[100];

void queen(int n);

void out();

int panduan(int n);

void main()

void queen(int n)

for(i=1;i<=a;i++)

}int panduan(int n)

return 1;

}void out()

printf("/n");}

以上就是8皇后的源程式，可以得知，n皇后問題就是8皇后問題的擴充套件，我們只需把程式中8*8棋盤變成n*n棋盤就行了。

現在畫出程式的框架圖。

是是 i++

否上面就是整個程式的原理框圖，下面我們來寫出整個程式。

#include<>

#define a x

int icount=0;

int x;

int site[100];

void queen(int n);

void out();

int panduan(int n);

void main()

void queen(int n)

for(i=1;i<=a;i++)

}int panduan(int n)

return 1;

}void out()

printf("/n");

}心得與體會：

解決這個問題，我們還是得從一些比較直觀的問題入手，其實n皇后最難的一點是你覺得這個n值是乙個變數，是乙個不確定的數，所以會感到比較抽象，但是只要你把這個n值想成8，轉換為我們熟知的8皇后問題，也就解決了問題的一大半，整個程式的思路和八皇后沒有太大的區別，

運用回溯法，雖然是解決了n皇后的問題，不過感覺程式執行效率並不高，每次放置皇后，都要做很多判斷，所以程式的複雜度相當繁瑣。

資料結構課程設計回溯法解決8皇后n皇后問題

資料結構課程設計

資料結構課程設計

資料結構課程設計

相關推薦