經典面試題目「回溯算法」N皇后問題

通知：我將公眾號文章和學習相關的資料整理到了Github ：https://github.com/youngyangyang04/leetcode-master，方便大家在電腦上學習，可以fork到自己倉庫，順便也給個star支持一波吧！

第51題. N皇后

題目連結：https://leetcode-cn.com/problems/n-queens/

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

上圖為 8 皇后問題的一種解法。

給定一個整數 n，返回所有不同的 n 皇后問題的解決方案。

每一種解法包含一個明確的 n 皇后問題的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。

示例: 輸入: 4
輸出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解釋: 4 皇后問題存在兩個不同的解法。

提示：
皇后，是西洋棋中的棋子，意味著國王的妻子。皇后只做一件事，那就是「吃子」。當她遇見可以吃的棋子時，就迅速衝上去吃掉棋子。當然，她橫、豎、斜都可走一到七步，可進可退。（引用自 百度百科 - 皇后 ）

思路

都知道n皇后問題是回溯算法解決的經典問題，但是用回溯解決多了組合、切割、子集、排列問題之後，遇到這種二位矩陣還會有點不知所措。

首先來看一下皇后們的約束條件：

1. 不能同行
2. 不能同列
3. 不能同斜線

確定完約束條件，來看看究竟要怎麼去搜索皇后們的位置，其實搜索皇后的位置，可以抽象為一棵樹。

下面我用一個3 * 3 的棋牌，將搜索過程抽象為一顆樹，如圖：

51.N皇后

從圖中，可以看出，二維矩陣中矩陣的高就是這顆樹的高度，矩陣的寬就是樹型結構中每一個節點的寬度。

那麼我們用皇后們的約束條件，來回溯搜索這顆樹，「只要搜索到了樹的葉子節點，說明就找到了皇后們的合理位置了」。

回溯三部曲

按照我總結的如下回溯模板，我們來依次分析：

void backtracking(參數) {    if (終止條件) {        存放結果;        return;    }    for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {        處理節點;        backtracking(路徑，選擇列表); // 遞歸        回溯，撤銷處理結果    }}

• 遞歸函數參數

我依然是定義全局變量二維數組result來記錄最終結果。

參數n是棋牌的大小，然後用row來記錄當前遍歷到棋盤的第幾層了。

代碼如下：

vector<vector<string>> result;void backtracking(int n, int row, vector<string>& chessboard) {

• 遞歸終止條件

在如下樹形結構中：

可以看出，當遞歸到棋盤最底層（也就是葉子節點）的時候，就可以收集結果並返回了。

代碼如下：

if (row == n) {    result.push_back(chessboard);    return;}

• 單層搜索的邏輯

遞歸深度就是row控制棋盤的行，每一層裡for循環的col控制棋盤的列，一行一列，確定了放置皇后的位置。

每次都是要從新的一行的起始位置開始搜，所以都是從0開始。

代碼如下：

for (int col = 0; col < n; col++) {    if (isValid(row, col, chessboard, n)) { // 驗證合法就可以放        chessboard[row][col] = 'Q'; // 放置皇后        backtracking(n, row + 1, chessboard);        chessboard[row][col] = '.'; // 回溯，撤銷皇后    }}

• 驗證棋牌是否合法

按照如下標準去重：

1. 不能同行
2. 不能同列
3. 不能同斜線 （45度和135度角）

代碼如下：

bool isValid(int row, int col, vector<string>& chessboard, int n) {    int count = 0;    // 檢查列    for (int i = 0; i < row; i++) { // 這是一個剪枝        if (chessboard[i][col] == 'Q') {            return false;        }    }    // 檢查 45度角是否有皇后    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {        if (chessboard[i][j] == 'Q') {            return false;        }    }    // 檢查 135度角是否有皇后    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {        if (chessboard[i][j] == 'Q') {            return false;        }    }    return true;}

在這份代碼中，細心的同學可以發現為什麼沒有在同行進行檢查呢？

因為在單層搜索的過程中，每一層遞歸，只會選for循環（也就是同一行）裡的一個元素，所以不用去重了。

那麼按照這個模板不難寫出如下代碼：

C++代碼

class Solution {private:vector<vector<string>> result;// n 為輸入的棋盤大小// row 是當前遞歸到棋牌的第幾行了void backtracking(int n, int row, vector<string>& chessboard) {    if (row == n) {        result.push_back(chessboard);        return;    }    for (int col = 0; col < n; col++) {        if (isValid(row, col, chessboard, n)) { // 驗證合法就可以放            chessboard[row][col] = 'Q'; // 放置皇后            backtracking(n, row + 1, chessboard);            chessboard[row][col] = '.'; // 回溯，撤銷皇后        }    }}bool isValid(int row, int col, vector<string>& chessboard, int n) {    int count = 0;    // 檢查列    for (int i = 0; i < row; i++) { // 這是一個剪枝        if (chessboard[i][col] == 'Q') {            return false;        }    }    // 檢查 45度角是否有皇后    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {        if (chessboard[i][j] == 'Q') {            return false;        }    }    // 檢查 135度角是否有皇后    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {        if (chessboard[i][j] == 'Q') {            return false;        }    }    return true;}public:    vector<vector<string>> solveNQueens(int n) {        result.clear();        std::vector<std::string> chessboard(n, std::string(n, '.'));        backtracking(n, 0, chessboard);        return result;    }};

可以看出，除了驗證棋盤合法性的代碼，省下來部分就是按照回溯法模板來的。

總結

本題是我們解決棋盤問題的第一道題目。

如果從來沒有接觸過N皇后問題的同學看著這樣的題會感覺無從下手，可能知道要用回溯法，但也不知道該怎麼去搜。

「這裡我明確給出了棋盤的寬度就是for循環的長度，遞歸的深度就是棋盤的高度，這樣就可以套進回溯法的模板裡了」。

大家可以在仔細體會體會！

就醬，如果感覺「代碼隨想錄」乾貨滿滿，就分享給身邊的朋友同學吧，他們可能也需要！

打算從頭開始打卡的錄友，可以在公眾號「算法匯總」這裡找到歷史文章，很多錄友都在從頭打卡，你並不孤單！

就醬，一直都是乾貨滿滿，公眾號裡的一抹清流，值得推薦給身邊的每一位同學朋友！