题目描述

算法1

DFS $O(n!)$

C++ 代码

    // row[i]=j：第i行的queen放在第j列
    // col[j]= true/false：第j列已经放置了queen

    vector<int> row;
    vector<bool> col;
    int res;

    // 在第i行放queen，枚举所有列
    void dfs(int i, int n) {
        if(i==n) { res++; return; }

        for(int j=0; j<n; j++) {
            // 检查列和对角线上是否已经有queen
            if(col[j] || diag(i, j, n)) continue;

            row[i] = j;
            col[j] = true;
            dfs(i+1, n);
            col[j] = false;
            row[i] = -1;
        }
    }

    // 如果queen放在(i,j)，与已有的queen，在对角线上是否有冲突
    bool diag(int i, int j, int n) {
        for(int r=0; r<n; r++){
            if(row[r]==-1) continue;
            if(abs(r-i) == abs(row[r]-j) ) return true;
        }
        return false;
    }

    int totalNQueens(int n) {
        row = vector<int>(n, -1);
        col = vector<bool>(n, false);

        dfs(0, n);
        return res;
    }