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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.