###### tags: `LeetCode` `Recursion` `Hard` `DFS` `String`
# LeetCode #51 [N-Queens](https://leetcode.com/problems/n-queens/)
### (Hard)

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

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

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


---

跟 [#37](https://hackmd.io/CDTAgNMPTkqUPXTv6yHXuQ) 數獨題類似, 重點同樣有兩個:
1. 如何遍歷整個棋盤
2. 如何判斷皇后的落點是合法的

有一個重點, DFS遞迴只能處理一維資料, 在#37中需要嘗試的資料有兩類
* 數字填入位置(而又將整個二維陣列透過進位轉成一維-行數等於n時呼叫下一列並將行數歸零)
* 每個位置又可以填入1-9
因此在 [#37](https://hackmd.io/CDTAgNMPTkqUPXTv6yHXuQ) 中透過一個for迴圈加上遞迴呼叫解決兩類資料。

在這題中, 將每一行獨立處理會輕鬆許多, 因此位置資料為二維矩陣, 而填入資料(皇后)不需要考慮差異(不像數獨題每個都要考慮1-9), 因此這題還是二維資料處理, 使用一個for迴圈加上遞迴呼叫即可。

前面提到用for迴圈加上遞迴, 對應到資料型態, 一個負責行(遞迴), 一個負責列(for迴圈), 因此, 程式碼為for迴圈從第0列開始, 每次遞迴檢查該行的皇后落點是否合法, 而終止條件為列數等於n(因為每一列都一定有一個皇后, 所以可以確定此時皇后數量已達最大值, 不需要額外檢查), 此時將棋盤存入答案數組中然後返回。

對應遍歷方式(由上層列往下層列, 每一列尋找該列能落子皇后的位置(行)), 在皇后落子合法性的檢查可以省去一些不必要的檢查, 如:同列(橫向)檢查(因為每一列都只會放一個皇后, 因此只要做前面幾列的同行(直向)檢查即可), 以及左下及右下檢查(因為是從上面列往下做, 因此下面列都還是空的, 只要檢查左上右上即可)。

最後, 在檢查左上右上時的for迴圈執行條件, (i>=0&&j<n)以及(i>=0&&j>=0), 要注意是用&&而非||, 因為for迴圈的第二個參數是執行條件而非終止條件, 使用||的話必須兩者皆不滿足才會停止, 會造成溢位。

---

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> tmp(n, string(n,'.'));
        vector<vector<string>> ans;
        dfs(ans, tmp, 0, n);
        return ans;
    }
    void dfs(vector<vector<string>>& ans, vector<string>& tmp, int row, int n){
        if(row==n){
            ans.push_back(tmp);
            return;
        }
        for(int column=0;column<n;column++)
                if(isvalid(tmp, row, column, n)){
                    tmp[row][column]='Q';
                    dfs(ans, tmp, row+1, n);
                    tmp[row][column]='.';
                }
    }
    bool isvalid(vector<string>& board, int row, int col, int& n){
        for(int i=0;i<row;i++){//直的
            if(board[i][col]=='Q')return false;
        }
        for(int i=row-1, j=col+1;i>=0&&j<n;i--,j++){//右上
            if(board[i][j]=='Q')return false;
        }
        for(int i=row-1, j=col-1;i>=0&&j>=0;i--,j--){//左上
            if(board[i][j]=='Q')return false;
        }
        return true;
    }
};