1、、問題 11、問題描述一、 N 皇后問題在 N*N 的棋盤上放置彼此不受攻擊的 N 個皇后。按照國際象棋的規則，皇 后可以攻擊與之處于同一行或同一列或同一斜線上的棋子。 N皇后的問題等價 于在 N*N 大小的棋盤中放置 N 個皇后，任何 2 個皇后都不放在同一行或同一列 或同一斜線上。使用隊列式分支限界法，求出 N 個皇后的一種放置方案。2、算法設計思想分支限界法解向量：因為皇后不能同行或同列，所以我們可以用這樣一個解向量來表示問題的解Xx1,x2xn x=1,2,3表示;1n行皇后位于的列數解空間：因為皇后不能同行同列，因此解空間為排列樹，使用廣度優先搜 索的方式搜索整棵樹剪枝函數：判斷新擺

2、放的皇后是否在已經擺放的皇后的斜線上3、算法過程描述第一行第一列放置皇后，這個節點成為拓展節點，產生 n-1 個活結點，加 入隊列，第一行第二列到第 n 列分別產生 n-1 個活結點，加入隊列，從隊列取 出第一個活結點，即第二行第二列，不滿足剪枝函數的要求，除去這個節點， 隊列中的節點依次取出，滿足剪枝函數的節點成為拓展節點產生活結點并加入 隊列，當成功進行到葉子節點時，就能得到問題的一個解，隊列為空時，就得 到了所有解4、算法實現及運行結果#include<iostream>#include<ctime>using namespace std;bool isOK(in

3、t n, int pieces)/ 剪枝函數/ 判斷當前狀態是否合理，即皇后會不會互相攻擊for (int i = 1; i <= n-1; i+)for (int j = i + 1; j <= n; j+)int left = -(j - i);/ 向左的斜線int right = (j - i);/ 向右的斜線if (piecesj = piecesi + left|piecesj = piecesi + right)/第i行皇后和第j行皇后會互相攻擊return false;/ 所有皇后都不會互相攻擊return true;void swap(int &a, int

4、 &b)int t = a;a = b;b = t;void nQueen(int n, int t, int pieces)if (t > n)for (int i = 1; i <= n; i+)for (int j = 1; j < piecesi; j+)cout << "- "cout << piecesi<<" "for (int j = piecesi + 1; j <= n; j+)cout << "- "cout << end

5、l;cout << endl;elsefor (int i = t; i <= n; i+)swap(piecest, piecesi);if (isOK(t, pieces)nQueen(n, t + 1, pieces);swap(piecest, piecesi);int main ()int n;cin >> n;int *pieces = new intn + 1;for (int i = 1; i <= n; i+)piecesi = i;nQueen(n, 1, pieces);cout << "OK" << endl;sys