一、問題描述

問題描述：在nn格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n皇后問題等價于在n*n的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。

算法設計：設計一個解n皇后問題的隊列式分支限界法，計算在nn個方格上放置彼此不受攻擊的n個皇后的一個放置方案。

*數據輸入：由文件input.txt給出輸入數據。第一行有1個正整數n。

*結果輸出：將計算的彼此不受攻擊的n個皇后的一個放置方案輸出到文件output.txt。文件的第一行是n個皇后的放置方案。

輸入文件：

input.txt

5

output.txt

1 3 5 2 4

二、問題分析
1.題目分析：

對于每一個放置點而言，它需要考慮四個方向上是否已經存在皇后。分別是行列，45度斜線和135度斜線。

行：每一行只放一個皇后，直到我們把最后一個皇后放到最后一行的合適位置，則算法結束。

列：列相同的約束條件，只需判斷j是否相等即可。

45度斜線和135度斜線：約束條件——當前棋子和已放置好的棋子不能存在行數差的絕對值等于列數差的絕對值的情況，若存在則說明兩個棋子在同一條斜線上

2.算法選擇：

用分支限界法來解決n皇后問題。對于該問題它滿足兩種樹結構。這里由于每一個合適的放置點出現最優解的概率是相等的，因此不需要使用優先隊列。編譯器提供了一個已經封裝好的隊列queue。

A.子集樹。我們把行約束條件和其它約束條件放在一起，即認為每一行，棋子都有n個位置可以放置。于是它的空間結構如下：

假設n=3，這個圖只畫出了兩層）

B.排列樹。我們把行約束條件單獨拿出來，也就是我們認為總共有八個皇后，這八個皇后必須都要放上去，但是放的位置不同，顯然這是一個排列樹。于是它的空間結構如下

這里由于我們還存在著其他的約束條件，并且行約束條件和這些條件完全可以放在一起，于是我就選擇了相對容易理解的子集樹作為解空間結構。

#include<iostream> #include<queue> #include<cmath> #include<vector> #include<fstream> #include<sstream> using namespace std;//定義一個節點類 struct Node{int number;vector<int>x;//保存當前解 }; //定義一個Queen的類 class Queen{friend int nQueen(int);public:bool Place(Node q,int n);void Research();int n;//皇后個數int *bestx;//最優解 }; //判斷是否能夠放置的函數 bool Queen::Place(Node q,int n) {for(int j=1;j<n;j++)if((abs(n-j)==abs(q.x[j]-q.x[n]))||(q.x[j]==q.x[n])) return false;return true; }void Queen::Research() {queue<Node>Q;//活節點隊列Node sign;sign.number=-1;Q.push(sign);//同層節點尾部標志int t=1;//當前節點所處的層Node Ew;//當前擴展節點 Ew.number=0; //搜索子集空間樹while(1){ //檢查所有的孩子節點 for(int k=1;k<=n;k++){//把當前擴展節點的值賦給下一個節點 Node q;q.number=t; q.x.push_back(0);//第一個位置為0 for(int i=1;i<t;i++) q.x.push_back(Ew.x[i]);q.x.push_back(k);if(Place(q,t))Q.push(q);} //取下一擴展節點,取出，賦值給Ew Ew=Q.front();Q.pop();if(Ew.number==-1){//同層節點尾部標記t++;//進入下一層 Q.push(sign);//增加標記//繼續往下去下一個節點 Ew=Q.front();Q.pop();} if(Ew.number==n){//找到最后一層的節點 for(int i=0;i<=n;i++) bestx[i]=Ew.x[i];break;} } }int nQueen(int n) {Queen X;X.n=n; X.bestx=new int[n+1];for(int i=0;i<=n;i++) X.bestx[i]=0;X.Research();for(int i=1;i<=n;i++){cout<<X.bestx[i]<<" ";} }int main(){int N;cout<<"輸入方格的行數："; cin>>N; cout<<"輸出計算的彼此不受攻擊的n個皇后的一個方案："; nQueen(N);return 0; }

總結

以上是生活随笔為你收集整理的算法设计与分析——分支限界法——n皇后问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。