51题求N皇后的解，这道题只要求有多少个解，不用求出来是哪一些解。

    我们把51题的稍微改一下就可以了

    1. class Solution {
    2.    vector<vector<string>> res;
    3.    int n;
    4.    void dfs(vector<bool>& col, vector<bool>& dig, vector<bool>& udig, vector<string>& v, int rownum)
    5.    {
    6.        if(rownum == n)
    7.        {
    8.            res.push_back(v);
    9.            return;
    10.        }
    11.        for(int j = 0; j < n; j++)
    12.        {
    13.            if(col[j] || dig[j - rownum + n] || udig[j + rownum])
    14.                continue;
    15.            v[rownum][j] = 'Q';
    16.            col[j] = dig[j - rownum + n] = udig[j + rownum] = true;
    17.            dfs(col, dig, udig, v, rownum + 1);
    18.            col[j] = dig[j - rownum + n] = udig[j + rownum] = false;
    19.            v[rownum][j] = '.';
    20.        }
    21.    }
    22. public:
    23.    int totalNQueens(int _n) {
    24.        n = _n;
    25.        int N = 2*n;
    26.        vector<bool> col(n,false), dig(N, false), udig(N, false);
    27.        vector<string> v(n, string(n, '.'));
    28.        dfs(col, dig, udig, v, 0);
    29.        return res.size();
    30.    }
    31. };

    还可以进行优化

    class Solution {
   int res;
   int n;
   void dfs(vector<bool>& col, vector<bool>& dig, vector<bool>& udig, int rownum)
   {
       if(rownum == n)
       {
           res++;
           return;
       }
       for(int j = 0; j < n; j++)
       {
           if(col[j] || dig[j - rownum + n] || udig[j + rownum])
               continue;
           col[j] = dig[j - rownum + n] = udig[j + rownum] = true;
           dfs(col, dig, udig, rownum + 1);
           col[j] = dig[j - rownum + n] = udig[j + rownum] = false;
       }
   }
public:
   int totalNQueens(int _n) {
       n = _n;
       vector<bool> col(n,false), dig(2*n, false), udig(2*n, false);
       dfs(col, dig, udig, 0);
       return res;
   }
};