# 51. N-Queens

N \* N格子要求每行每列放置一个元素，同行同列以及斜着不能有其它元素，问所有的放置方法。找所有可能，DFS。对当前row, 选择好每个可能的col后，DFS下一行。 配合三个visited set排除已经flag过不能再走的，分别是已经有过的列，45°斜和135°斜。

```cpp
/*
 * @lc app=leetcode id=51 lang=cpp
 *
 * [51] N-Queens
 */
class Solution {
public:
    void dfs(const int n, int r, vector<bool> &cols, vector<bool> &diags1, vector<bool> &diags2, vector<string> &path, vector<vector<string>> &res) {
        if (r == n) {
            res.push_back(path);
            return;
        }
        for (int c = 0; c < n; ++c) {
            const int diag1 = r + c, diag2 = c - r + n - 1;
            if (cols[c] || diags1[diag1] || diags2[diag2]) continue;
            cols[c] = true;
            diags1[diag1] = true;
            diags2[diag2] = true;
            const string q = string(c, '.') + "Q" + string(n - 1 - c, '.');
            path.push_back(q);
            dfs(n, r + 1, cols, diags1, diags2, path, res);
            cols[c] = false;
            diags1[diag1] = false;
            diags2[diag2] = false;
            path.pop_back();
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<bool> cols(n), diags1(2 * n - 1), diags2(diags1);
        vector<string> path;
        vector<vector<string>> res;
        dfs(n, 0, cols, diags1, diags2, path, res);
        return res;
    }
};


```


---

# 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://hao-fu-1.gitbook.io/oj/exhaustive-search/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.