题目

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：
image.png

  1. 输入：n = 4
  2. 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
  3. 解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

  1. 输入：n = 1
  2. 输出：[["Q"]]

提示：

  • 1 <= n <= 9

    解题方法

    递归回溯+哈希表

    使用哈希表记录当前行、列、左右斜线上是否存在皇后，通过递归回溯分行处理穷举所有可能。
    时间复杂度O(n!)，空间复杂度O(n)
    C++代码： ```cpp class Solution { private: vector cur; vector> result; int col[9] = {0}; int diag_ji[17] = {0}; int diag_ij[17] = {0};

public: void build_map(int n) { string tmp = “”; for(int i=0; i<n; i++) tmp+=”.”; for(int i=0; i<n; i++) cur.push_back(tmp); }

void backtracking(int n, int num, int i) {
    if(num==n) {
        result.push_back(cur);
        return;
    }
    if(i==n) return;
    for(int j=0; j<n; j++) {
        if(col[j] || diag_ji[j-i+(n-1)] || diag_ij[i+j]) continue;
        col[j] = 1;
        diag_ji[j-i+(n-1)] = 1;
        diag_ij[i+j] = 1;
        cur[i][j] = 'Q';
        backtracking(n, num+1, i+1);
        cur[i][j] = '.';
        col[j] = 0;
        diag_ji[j-i+(n-1)] = 0;
        diag_ij[i+j] = 0;
    }
}

vector<vector<string>> solveNQueens(int n) {
    build_map(n);
    backtracking(n, 0, 0);
    return result;
}

};

<a name="J1fl6"></a>
## 递归回溯+位运算优化
通过位运算记录行、列、对角线占用情况。<br />时间复杂度`O(n!)`，空间复杂度`O(n)`<br />**C++代码：**
```cpp
class Solution {
private:
    vector<string> cur;
    vector<vector<string>> result;
    int col = 0;
    int diag_ji = 0;
    int diag_ij = 0;

public:
    void build_map(int n) {
        string tmp = "";
        for(int i=0; i<n; i++)  tmp+=".";
        for(int i=0; i<n; i++)  cur.push_back(tmp);
    }

    void backtracking(int n, int num, int i) {
        if(num==n) {
            result.push_back(cur);
            return;
        }
        if(i==n) return;
        for(int j=0; j<n; j++) {
            if( (col&(1<<j)) || (diag_ji&(1<<(j-i+(n-1)))) || (diag_ij&(1<<(i+j)))) continue;
            col^=(1<<j);
            diag_ji^=(1<<(j-i+(n-1)));
            diag_ij^=(1<<(i+j));
            cur[i][j] = 'Q';
            backtracking(n, num+1, i+1);
            cur[i][j] = '.';
            col^=(1<<j);
            diag_ji^=(1<<(j-i+(n-1)));
            diag_ij^=(1<<(i+j));
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        build_map(n);
        backtracking(n, 0, 0);
        return result;
    }
};