# 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;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/leetcode/51.-n-queens.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.