> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/51.-n-queens.md).

# 51. N-Queens

## 1.問題 

* n queen

![](/files/-LNDvdFzlWticomIib2T)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 確認題意:  col, row, diagonal都只能有一個queen
* parameter
* * record list
  * res list
  * n
  * new row (new col在程式中)
  * col list (存放已經放入的queen的位置)
* test input
* 說明想法
  * isValid function:&#x20;
    * 檢查col:&#x20;
      * col list的index是row, value是col, 由於在相同row下我們只有放一個queen, 因此檢查時只需要檢查col有沒有collision
    * 檢查對角線: 新位置跟array中的所有值去比較, col的差值不可以等於row的差值
  * solveHQ function
    * DFS
      * base case: 當new row == n表示所有row都擺上了queen,  push record到res中
        * ray tracking: 在每一輪中嘗試對new row的不同col放置queen, 若能通過isValid, 則push到record及col中, 進到下一輪迭帶, 如同別的DFS + ray tracking題目, 要記得pop回來
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> record;
        vector<int> col;
        solveHQ(n, 0, res, record, col);
        return res;
    }
private:
    //假設棋盤為正方形, 依序填完第0個row後, 再換下個row, 共填n個row
    void solveHQ(int n, int newRow, vector<vector<string>>& res, vector<string>& record, vector<int>& col){
        if (newRow == n) {
            res.push_back(record);
            return;
        }
        
        for (int i = 0; i <n; i++) {
            if (isValid(col, i, newRow)) {
                //填入Q
                string s(n, '.');
                s[i] = 'Q';
                record.push_back(s);
                col.push_back(i);
                solveHQ(n, newRow + 1, res, record, col);
                record.pop_back();
                col.pop_back();
            }
        }
    }
    
    //確認new col的位置是否合法
    //用一個vector來存放col, row的值: index代表第幾個row, col[index]代表第幾個col
    bool isValid(vector<int> col, int newCol, int newRow) {
        for (int i = 0; i <col.size(); i++) {
            if (col[i] == newCol ||
                abs(i - newRow) == abs(col[i] - newCol)) {
                //對角線: 當row差值等於col差值時
                return false;
            }
        }
        return true;
    }
};
```