题目描述

$n$-皇后问题是将 $n$ 个皇后放在 $n*n$ 的棋盘上，使得皇后不能相互攻击到。

给定一个整数 $n$，返回所有 $n$-皇后问题的合法方案。
每个方案包含一个不同的放置 $n$ 个皇后的方法，用 'Q' 表示皇后，'.'表示空格。

样例

输入：

4

输出：

[
 [".Q..",  // 方案1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 方案2
  "Q...",
  "...Q",
  ".Q.."]
]

解释：4-皇后问题一共包含上述两种方案。

算法

(暴力搜索) $O(n!)$

暴力搜索所有方案。
为了优化时间效率，定义 vector<bool>row, col, diag, anti_diag;，用来记录每一行、每一列、每条对角线上是否有皇后存在。

搜索时需要记录4个状态：$x, y, s, n$，分别表示横纵坐标、已摆放的皇后个数、棋盘大小。
对于每步搜索，有两种选择：

1. 当前格子不放皇后，则转移到 dfs(x, y + 1, s, n);
2. 如果 $(x, y)$ 所在的行、列、对角线不存在皇后，则当前格子可以摆放皇后，更新row, col, diag, anti_diag后转移到 dfs(x, y + 1, s + 1, n);，回溯时不要忘记恢复row, col, diag, anti_diag等状态。

时间复杂度分析：由于 $n$ 个皇后不能在同行同列，所以每行恰有一个皇后，我们计算一下在不考虑对角线的情况下，方案数的上限：第一行有 $n$ 个位置可选，第二行有 $n - 1$ 个位置可选，依次类推，可得方案数最多是 $n!$。所以时间复杂度是 $O(n!)$。

C++ 代码

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> path;
    vector<bool> row, col, diag, anti_diag;

    vector<vector<string>> solveNQueens(int n) {
        row = col = vector<bool>(n, false);
        diag = anti_diag = vector<bool>(2 * n, false);
        path = vector<string>(n, string(n, '.'));
        dfs(0, 0, 0, n);
        return ans;
    }

    void dfs(int x, int y, int s, int n)
    {
        if (y == n) x ++ , y = 0;
        if (x == n)
        {
            if (s == n) ans.push_back(path);
            return ;
        }

        dfs(x, y + 1, s, n);
        if (!row[x] && !col[y] && !diag[x + y]
                && !anti_diag[n - 1 - x + y])
        {
            row[x] = col[y] = diag[x + y]
                = anti_diag[n - 1 - x + y] = true;
            path[x][y] = 'Q';
            dfs(x, y + 1, s + 1, n);
            path[x][y] = '.';
            row[x] = col[y] = diag[x + y]
                = anti_diag[n - 1 - x + y] = false;
        }
    }
};