题解 | #N皇后问题#

回溯

从第一行开始枚举皇后放在哪一列

递归函数：dfs(int x)

1. 如果当前行 x 等于 n 表示所有行的皇后都已经放完了，则方案数 + 1，将当前棋盘加入到答案中。

2. 枚举皇后应该放在 x 行的哪一列 y，y 从 0 枚举到 n - 1

   • 判断：如果当前列 col[y]、当前对角线 dg[y - x + n]、当前反对角线udg[y + x] 上没有皇后

     • 这个位置才可以放皇后 g[x][y] = 'Q'，
     • 然后设置 col[y] = dg[y -x + n] = udg[y + x] = true，
     • 递归枚举下一行 dfs(x + 1)，
     • 最后别忘记回溯 col[y] = dg[y -x + n] = udg[y + x] = false g[x][y] = '.'

   • 否则枚举下一列

class Solution {
public:
    int n;
    vector<vector<string>> ans;
    vector<string> g;
    vector<bool> col, dg, udg;
    int res = 0;
    
    void dfs(int x) {
        if (x == n) {
            ans.push_back(g);
            res ++ ;
            return;
        }
        
        for (int y = 0; y < n; y ++ ) {
            if (!col[y] && !dg[y - x + n] && !udg[y + x]) {
                g[x][y] = 'Q';
                col[y] = dg[y - x + n] = udg[y + x] = true;
                dfs(x + 1);
                col[y] = dg[y - x + n] = udg[y + x] = false;
                g[x][y] = '.';
            }
        }
    }
    
    int Nqueen(int _n) {
        n = _n;
        g = vector<string>(n, string(n, '.'));
        col = vector<bool>(n, false);
        dg = udg = vector<bool>(2 * n - 1, false);
        // 从第 1 行开始枚举当前行皇后的位置
        dfs(0);
        
//         for (auto item : ans) {
//             for (auto line : item)
//                 cout << line << endl;
//             cout << endl;
//         }
        
        return res;
    }
};