class Solution {
public:
    int result = 0;
    vector<pair<int , int>> path;
    void track_back(int n , int deep )
    {
        if(deep > n) return;
        if(deep == n) result++;
        for(int i=0 ; i<n ;i++)
        {
            pair<int,int> tmp(deep,i);
            bool flag = true;
            for(auto it:path)
            {
                if( deep == it.first  || i == it.second
                    || abs(deep - it.first) == abs(i - it.second) )
                {
                    flag = false;
                    break;
                }
            }
            if(flag == true)
            {
                path.push_back(tmp);
                track_back(n,deep+1);
                path.pop_back();
            }
        }
        return;
    }
    int totalNQueens(int n) {
        track_back(n,0);
        return result;
    }
};