一：題目 Come 寶！！！！！！！！！！！！

在N*N的方格棋盤放置了N個皇后，使得它們不相互攻擊（即任意2個皇后不允許處在同一排，同一列，也不允許處在與棋盤邊框成45角的斜線上。 你的任務(wù)是，對于給定的N，求出有多少種合法的放置方法

輸入格式:
共有若干行，每行一個正整數(shù)N≤10，表示棋盤和皇后的數(shù)量；

輸出格式:
共有若干行，每行一個正整數(shù)，表示對應(yīng)輸入行的皇后的不同放置數(shù)量

輸入樣例:
在這里給出一組輸入。例如：

1 8 5

結(jié)尾無空行
輸出樣例:
在這里給出相應(yīng)的輸出。例如：

1 92 10

二:關(guān)于輸入

這里只要輸入一個值有一個結(jié)果即可，嗯嗯就是這樣的

三：思路

思路:
1.這里在選擇建樹(也就是在選擇解的空間上)是 子集樹
2.那么在結(jié)點上我們選擇的是一個二維的矩陣就是將最后的結(jié)果落實到一個二維容器里
也就遍歷到葉節(jié)點時候一種可行解的情況
3.寫碼思路：
<1>:遞歸函數(shù)的參數(shù):
backtacking(int row,vector &v,int n)
row:代表矩陣的行數(shù)
vector &v:存放的是最后二維矩陣的可行解
n:代表的是棋盤的寬度和長度
<2>:輸出結(jié)果
這里使用 vector<vector> v;
來處理每次的可行接
<3>:單層循環(huán)
這里橫向每層的循環(huán)是遍歷不同的列，橫向的是遞歸二維矩陣不同的行（往下進行）
<4>:遞歸終止條件
當 row == n 時候，我們就可以將一次可行解裝入容器了

4.這里還需補充的是在遞歸函數(shù)里，我們在每次選擇皇后的位置的時候要注意題目的要求
不同行，不同列 不在同一條斜線上
不同行:因為我們是逐層往下遞歸的所以不同行我們就解決了
不同列:這里看代碼
不在一條斜線上:(分為45° 和 135°) 這里圖解

四:上碼

/**思路:1.這里在選擇建樹(也就是在選擇解的空間上)是 子集樹2.那么在結(jié)點上我們選擇的是一個二維的矩陣就是將最后的結(jié)果落實到一個二維容器里也就遍歷到葉節(jié)點時候一種可行解的情況3.寫碼思路：1>:遞歸函數(shù)的參數(shù):backtacking(int row,vector<string> &v,int n)row:代表矩陣的行數(shù)vector<string> &v:存放的是最后二維矩陣的可行解n:代表的是棋盤的寬度和長度2>:輸出結(jié)果這里使用 vector<vector<string >> v;來處理每次的可行接3>:單層循環(huán)這里橫向每層的循環(huán)是遍歷不同的列，橫向的是遞歸二維矩陣不同的行（往下進行）4>:遞歸終止條件當 row == n 時候，我們就可以將一次可行解裝入容器了4.這里還需補充的是在遞歸函數(shù)里，我們在每次選擇皇后的位置的時候要注意題目的要求不同行，不同列 不在同一條斜線上不同行:因為我們是逐層往下遞歸的所以不同行我們就解決了不同列:這里看代碼不在一條斜線上:(分為45° 和 135°) 這里圖解 **/#include<bits/stdc++.h> using namespace std;vector<vector<string> > ans;//判斷位置是否合法 bool isLegal(int row,int cal,vector<string> &v,int n){//判斷是否在一列上for (int i = 0; i < row; i++) {//這里我們只判斷從row往上的行即可if (v[i][cal] == 'Q') return false;}//判斷是否在135°斜線上上for (int i = row - 1, j = cal - 1; i >= 0 && j >= 0; i--,j--) {if (v[i][j] == 'Q') return false;}//判斷是否在45°斜線上for (int i = row - 1,j = cal + 1; i >= 0 && j <= n; i--,j++){if (v[i][j] == 'Q') return false;}return true; }void backtacking(int row,vector<string> &v,int n) {if (row == n) {ans.push_back(v);return;}for (int cal = 0; cal < n; cal++) {//cal:列if (isLegal(row,cal,v,n)) {v[row][cal] = 'Q';//這是滿足條件的backtacking(row+1,v,n);v[row][cal] = '.';//當一次可行結(jié)果 結(jié)束后，需要v將空間騰出來，給后面的可行解 }} }void solveNQueens(int n) {vector<string>v (n,string(n,'.'));//這傳入的就是默認的二維矩陣..backtacking(0,v,n);// return ans;}int main(){int N;cin >> N;solveNQueens(N);cout << ans.size();}

五:貼心杰來補充了

1:碼中 ‘Q’

寶 如果這道題有些地方看不懂比如題目中輸入的 Q 什么的，那是我先AC的leedcode上的一道題，做出來那道后，我就直接改了改，就拿來了，如果實在看不懂可以看看下面 這個題解，也是N皇后問題
leedcodeN皇后

2:碼中還有一個是vector path （n,string(n,’.’)）

vector path （n,string(n,’.’)）：中（n,string(n,’.’)）這部分就是一個初始化
用這個容器的時候 你可能不太懂，其實那就是 一個 二維數(shù)組，用來存每次的可行解的，你想想寶 ，我們每次的結(jié)果都是在二維矩陣中的一些位置，所以我們肯定需要一個二維的容器來記錄啊！！
得虧我是寵粉杰啊，直接上示例，

#include<bits/stdc++.h> using namespace std;int main(){vector<string> v(5,string(5,'.'));for(int i = 0; i < 5; i++){for(int j = 0; j < 5; j++){cout << v[i][j] << ' ';}cout << endl;}}

加油 寶！！！

總結(jié)

以上是生活随笔為你收集整理的7-4 N皇后 (28 分)(思路+详解)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。