本题同八皇后问题的区别在于：当某一位置的对角线和反对角线有皇后时，也不一定 就一定不能在该位置放皇后，还要判断行号差是否>=3

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
typedef long long LL;
LL n,m;
const int N = 20;
int col[N],dg[N*2],udg[N*2];
vector<int> dgr,udgr;//存放已经防止皇后的位置的行号（二者存放的元素相同，只保留一个也可以，分着写更清晰）
int res;
void dfs(int u)
{
    if(u==n)
    {
        res++;
        return ;
    }
    for(int j=0;j<n;j++)
    {
        bool bp=dg[u+j],bpu=udg[j-u+n];
        if(dg[u+j]) //对角线有元素，判断是否能在(i,j)上放置皇后
        {
            bool flag=false;
            for(auto t:dgr)
                if(abs(t-u)<3) 
                {
                    flag=true;
                    break;
                }

            if(!flag)
            dg[u+j]=false;//可以放
        }
        if(udg[j-u+n])//反对角线有元素，判断是否能在(i,j)上放置皇后
        {
            bool flag=false;
            for(auto t:udgr)
                if(abs(t-u)<3) 
                {
                    flag=true;
                    break;
                }

            if(!flag)
            udg[j-u+n]=false;
        }
        if(!col[j]&&!dg[u+j]&&!udg[j-u+n])
        {
            col[j]=dg[u+j]=udg[j-u+n]=true;
            dgr.push_back(u),udgr.push_back(u);
            dfs(u+1);
            dg[u+j]=bp,udg[j-u+n]=bpu,col[j]=false;
            dgr.pop_back(),udgr.pop_back();
        }
    }
}
int main()
{
    cin>>n;
    dfs(0);
    cout<<res<<endl;
    return 0;
}