题解 | N皇后问题

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 the n
     * @return int整型
     */
    void BackTrack(int n,int row,unordered_set<int>& cols,unordered_set<int>& diag1,unordered_set<int>& diag2,int& counter)
    {
      if(row==n)//每行放一个，所有行都放完了
      {
        counter++;
        return;
      }
      //对列进行遍历，寻找能放的列
      for(int i=0;i<n;i++)
      {
        int d1=row-i;//主对角线的差值，用来防止在主对角线上
        int d2=row+i;//副对角线的和值，用来防止在副对角线上
        if(cols.count(i)||diag1.count(d1)||diag2.count(d2))//判断当前列是否已经存在，主对角线和副对角线上是否已经存在
        {
            continue;
        }
        //说明当前列没有问题，更新cols、diag1、diag2
        cols.insert(i);
        diag1.insert(d1);
        diag2.insert(d2);
        //递归找下一行
        BackTrack(n,row+1,cols,diag1,diag2,counter);
        //递归结束，说明找完了一次，此时要回溯
        cols.erase(i);
        diag1.erase(d1);
        diag2.erase(d2);
      }

    }
    int Nqueen(int n) {
        // write code here
        if(n<=0)
        {
            return 0;
        }
        unordered_set<int> cols;
        unordered_set<int> diag1;
        unordered_set<int> diag2;
        int counter=0;
        BackTrack(n,0,cols,diag1,diag2,counter);
        return counter;
    }
};