52. N 皇后 II

题解

class Solution {
public:
    int totalNQueens(int n) {
         int ans = 0;
         vector<int> queens(n);
         vector<int> col(n), diag1(2 *n-1), diag2(2*n - 1);
         auto dfs = [&](auto && dfs, int r){
            if (r == n)
            {
                ans ++;
                return;
            }
            for(int c = 0 ; c < n; c ++)
            {
                int d2 = r - c + n - 1;
                if (!col[c] && !diag1[r + c] && ! diag2[d2])
                {
                    queens[r] = c;
                    col[c] = diag1[r + c] = diag2[d2] = true;
                    dfs(dfs, r+1);
                    col[c] = diag1[r + c] = diag2[d2] = false; 
                } 
            }
         };
         dfs(dfs, 0);
         return ans;
    }
};

思路

这是一个典型的回溯思想的题

DFS

首先需要确立一个dfs遍历目标，需要知道的是选择位置，其实就是不同行上的皇后位置的全排列，代码中记为queens数组，queens[r] = c表示第r行上皇后的位置是c。

所以在这个基础上，我们只需要知道不能放的位置是什么。对此，需要三个数组，col[i]==true表示第i列上已经有皇后了，diag1是皇后的行列之和即r+c，diag2是皇后的行列之差r-c（为了方便数组索引，不让计算结果为负，所以需要+(n-1)）。

col容易理解，但是，diag1和diag2怎么理解呢？其实画图就可以发现，如果两个位置(r1,c1)和(r2,c2)在斜方向上冲突，则r1+c1 == r2+c2或者r1-c1 == r2-c2，这一点本质上可以通过向量来推导出，即两点连线的向量与两个斜单位向量之一垂直。

有了这些接下来就简单了，只需要dfs遍历判断并且回溯。