n 皇后問題 研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

給你一個整數 n ，返回所有不同的 n 皇后問題 的解決方案。
每一種解法包含一個不同的 n 皇后問題 的棋子放置方案，該方案中 ‘Q’ 和 ‘.’ 分別代表了皇后和空位。

示例 1：

輸入：n = 4
輸出：[[".Q…","…Q",“Q…”,"…Q."],["…Q.",“Q…”,"…Q",".Q…"]]
解釋：如上圖所示，4 皇后問題存在兩個不同的解法。

示例 2：
輸入：n = 1
輸出：[[“Q”]]

提示：

1 <= n <= 9
皇后彼此不能相互攻擊，也就是說：任何兩個皇后都不能處于同一條橫行、縱行或斜線上。

N皇后問題是典型的回溯問題， 解決回溯問題最好的方法就是先能畫出樹狀圖，這道題的畫法是這這樣的如圖：

每一列通過for循環進行遍歷，每一行通過遞歸進行遍歷，這里畫不下了，知道怎么畫就行了；

那么這道題只要找到最后的葉子節點，就是答案之一了；

遞歸結束條件通過畫圖也很容易發現，只要遞歸的層數row等于n時，就到了葉子節點了；

然后就可以通過for循環確定每一列column，遞歸確定每一行row，這樣通過行列是否滿足棋盤規則就可以確定每個位置能不能放皇后Q了；

這個棋盤規則也很簡單，就是三點
1，不能同行
2，不能同列
3，不能同斜線 （45度和135度角）

這里面我們其實并不需要對行進行檢查，因為每一次的遞歸，行數都會相應增加，所以在一次次遞歸中，行的檢查就已經通過列的檢查覆蓋完了；

其他就沒有什么難度了，這道題只要能想到這個圖怎么畫的，知道行和列的關系就沒有問題了；
詳細注釋在代碼里，可以比較著看
代碼如下：

class Solution { private: vector<vector<string>> ans;//n是棋盤大小，row是遞歸到的行數void backTracking(int n, int row, vector<string>& chessboard) {//當行數為棋盤的最后一行時，遞歸結束if (row == n) {ans.push_back(chessboard);return ;}//for循環是對每一列column進行的遍歷，就是類似于寬度，//遞歸則是對每一行row進行的遍歷，及深度的遍歷for (int column = 0; column < n; ++column) {//如果該行row該列column這個位置合法，就可以放皇后Qif (isValid(row, column, chessboard, n)) {chessboard[row][column] = 'Q';backTracking(n, row + 1, chessboard);//遞歸chessboard[row][column] = '.';//回溯}}}//判斷是否合法bool isValid(int row, int column, vector<string>& chessboard, int n) {//檢查第column列有沒有Q出現for (int i = 0; i < row; ++i) {if(chessboard[i][column] == 'Q')return false;}//檢查左斜線有沒有Q（45度）for (int i = row - 1, j = column - 1; i >= 0 && j >=0; --i, --j) {if (chessboard[i][j] == 'Q') return false;}//檢查右斜線有沒有Q（135度）for (int i = row - 1, j = column + 1; i >= 0 && j < n; --i, ++j) {if (chessboard[i][j] == 'Q')return false;}return true;} public:vector<vector<string>> solveNQueens(int n) {vector<string> chessboard(n, string(n, '.'));backTracking(n, 0, chessboard);return ans;} };

這種問題就屬于棋盤類的問題，有一道相似的題目可以嘗試一下：37. 解數獨
這個題目其實是在原集合里進行的修改，所以不需要定義額外的變量，可以嘗試一下；
帶有詳細注釋的代碼貼上：

class Solution { private:bool backTracking(vector<vector<char>>& board) {//分別對行和列進行遍歷，遞歸則是對這9個數進行的遍歷for (int i = 0; i < board.size(); ++i) {for (int j = 0; j < board[0].size(); ++j) {//如果這個位置有數，就跳過if (board[i][j] != '.') continue;//對9個數進行遍歷for (char ch = '1'; ch <= '9'; ++ch) {//當前的數符合要求的話，就放到當前位置if (isVaild(i, j, ch, board)) {board[i][j] = ch;//當遞歸到底找到了合適的一組后返回if (backTracking(board)) return true;board[i][j] = '.';//回溯}}return false;//試完了9個數，都不滿足，則放回false}}return true;//若結束了遍歷沒有返回false，則說明找到了合適的答案}bool isVaild(int row, int column, char ch, vector<vector<char>>& board) {//判斷列是否有重復for (int i = 0; i < 9; ++i) {if (board[i][column] == ch)return false;}//判斷行是否有重復for (int i = 0; i < 9; ++i) {if (board[row][i] == ch) return false;}//針對每一個小九宮格，判斷里面是否出現重復的元素int startRow = (row / 3) * 3;int startColumn = (column / 3) * 3;for (int i = startRow; i < startRow + 3; ++i) {for (int j = startColumn; j < startColumn + 3; ++j) {if (board[i][j] == ch)return false;}}return true;} public:void solveSudoku(vector<vector<char>>& board) {backTracking(board);} };

在力扣上一看還有一個N皇后||，和N皇后可以說一模一樣，小改動一下就可以了，感覺比N皇后簡單；
代碼如下：

class Solution { private: int ans = 0;void backTracking(int n, int row, vector<string>& chessboard) {if (row == n) {ans++;return ;}for (int column = 0; column < n; ++column) {if (isVaild(n, row, column, chessboard)) {chessboard[row][column] = 'Q';backTracking(n, row + 1, chessboard);chessboard[row][column] = '.';}}}bool isVaild(int n, int row, int column, vector<string>& chessboard) {for (int i = 0; i < row; ++i) {if (chessboard[i][column] == 'Q')return false;}for (int i = row - 1, j = column - 1; i >= 0 && j >= 0; --i, --j) {if (chessboard[i][j] == 'Q')return false;}for (int i = row - 1, j = column + 1; i >= 0 && j < n; --i, ++j) {if (chessboard[i][j] == 'Q')return false;}return true;} public:int totalNQueens(int n) {vector<string> chessboard(n, string(n, '.'));backTracking(n, 0, chessboard);return ans;} };

注意：下面啥也不是

評論區看到了一個面向測試編程🙈，擊敗百分百
代碼如下（java）

class Solution {public int totalNQueens(int n) {int[] rs = new int[]{0,1,0,0,2,10,4,40,92,352,724,2680};return rs[n];} }

總結

以上是生活随笔為你收集整理的51. N 皇后（回溯算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

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