搜索、位运算、状态压缩

状压棋盘状态、列状态和两种斜线状态，枚举行放置皇后，位运算 $O(1)$ 找到可放置的位置。

时间复杂度 $O(n!)$。

#include<bits/stdc++.h>
using namespace std;
int n,ans,sta,m[15];
void dfs(int x,int lr,int lh,int rh){
    if(x==n) return ++ans,void();
    for(int i=m[x]&lr&lh&rh;i;i-=i&-i){
        int nxtl=((lh^(i&-i))<<1)|1,nxtr=((rh^(i&-i))>>1)|(1<<(n-1));
        dfs(x+1,lr^(i&-i),nxtl,nxtr);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        static char s[16];
        scanf("%s",s);
        for(int j=0;j<n;j++) if(s[j]=='*') m[i]|=1<<j;
        sta|=1<<i;
    }
    dfs(0,sta,sta,sta);
    printf("%d\n",ans);
    return 0;
}