分析

• 本题的考点：递归回溯。

• 递归过程中我们依次枚举每行，然后看这一行中皇后可以放置在哪个位置。

• 对于当前枚举的某行u，如果判断该行中的第i列是否可以放置一个皇后呢？可以使用三个数组col、dg、udg表示列、左上到右下斜线、右上到左下斜线中是否放置了皇后。坐标转化关系如下：

代码

• C++

class Solution {
public:
    int n;
    vector<bool> col, dg, udg;
    vector<vector<string>> ans;
    vector<string> path;

    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        col = vector<bool>(n);
        dg = udg = vector<bool>(n * 2 - 1);
        path = vector<string>(n, string(n, '.'));

        dfs(0);
        return ans;
    }

    void dfs(int u) {
        if (u == n) {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i < n; i ++ ) {
            if (!col[i] && !dg[u - i + n - 1] && !udg[u + i]) {
                col[i] = dg[u - i + n - 1] = udg[u + i] = true;
                path[u][i] = 'Q';
                dfs(u + 1);
                path[u][i] = '.';
                col[i] = dg[u - i + n - 1] = udg[u + i] = false;
            }
        }
    }
};

• Java

class Solution {

    int n;
    boolean[] col, dg, udg;
    List<List<String>> ans = new ArrayList<>();
    char[][] path;

    public List<List<String>> solveNQueens(int _n) {

        n = _n;
        col = new boolean[n];
        dg = new boolean[n * 2 - 1]; udg = new boolean[n * 2 - 1];
        path = new char[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(path[i], '.');

        dfs(0);
        return ans; 
    }

    // 当前考察第u行
    private void dfs(int u) {
        if (u == n) {
            List<String> t = new ArrayList<>();
            for (int i = 0; i < n; i++) t.add(new String(path[i]));
            ans.add(t);
            return;
        }

        for (int i = 0; i < n; i++) 
            if (!col[i] && !dg[u - i + n - 1] && !udg[u + i]) {
                col[i] = dg[u - i + n - 1] = udg[u + i] = true;
                path[u][i] = 'Q';
                dfs(u + 1);
                path[u][i] = '.';
                col[i] = dg[u - i + n - 1] = udg[u + i] = false;
            }
    }
}

时空复杂度分析

• 时间复杂度：指数级别的。

• 空间复杂度：和递归深度有关。