还是 N 皇后
题目描述
正如题目所说，这题是著名的 $N$ 皇后问题。
输入格式
第一行有一个 $N$。接下来有 $N$ 行 $N$ 列描述一个棋盘，* 表示可放，. 表示不可放。
输出格式
输出方案总数。
样例 #1
样例输入 #1
4
**.*
****
****
****样例输出 #1
1提示
$0< n\le14$
题目分析
目的：求出 $N$ 皇后的方案总数。
对于 $N$ 皇后问题，要求是每行、每列有且只有一个棋子，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。并且在本道题目中，还额外对一些位置做了要求，有些位置可以放置棋子，有些位置不能放置棋子。
由于每一行只能放置一个棋子，每列也是只能放置一个棋子，若我们从第一行到最后一行将棋子放置的列号写出，可发现是一个由 $1\sim n$ 的不重复数字组成的数列。所有的排列情况即 $n$ 的全排列，时间复杂度为 $O(n!)$，在题目规模下必然会超时。我们需要寻找优化的方法。
暴搜框架
void dfs(int d){//d-已放置的棋子个数
if(d==n){//已放置n个棋子
//输出
return 0;
}
for(int i=1;i<=n;i++){
if(chk(i)){
//判断(d+1,i)是否可放置
//相关标记处理
dfs(d+1);
//回溯处理
}
}
}在暴力搜索的过程中，有一个过程是存在重复处理的，就是每一行一列列判断棋盘位置是否可放置棋子的这一步。随着棋子放置个数的增多，棋盘上实际可放置的位置会越来越少，而程序依旧需要 $1\sim n$ 逐个去进行遍历。若能直接定位到未放置的位置，省略了中间遍历寻找的过程，速度自然大大加快。
仔细观察，可发现，实际上每个位置无非两种情况：
- 可以放
- 不能放
列数最多为 $13$ 列，不是很多，我们可以用状态压缩的思想去记录每一列棋子放置情况。另外，位运算操作中有一个技巧，它能跳过低位的 $0$ ，直接定位到最低位的 $1$。它就是 lowbit 操作。
int lowbit(int x){//返回x二进制对应的最低位的1
return x&-x;
}此时，我们可以将能放的位置处理为 $1$,不能放的处理为 $0$,再利用lowbit操作即可实现加速的要求。
for(int i=state;i;i-=lowbit(i))//遍历state 中的二进制1
{
int x=lowbit(i);
//......
}对于本题，还有一个难点在于对角线不能重复，对角线分两条，一条左倾，一条右倾。该如何在二进制状态中描述对角线的影响呢？
仔细观察，对于左倾对角线，在某行 $y$ 列占位，那么影响的是下一行 $y+1$ 列，也就是只要右移一位就好。对应的右倾对角线也只要左移一位就好。
代码实现
#include<bits/stdc++.h>
using namespace std;
int a[15];//每一行对放置位置限制的状压表示
int n,ans,all;
int lowbit(int x){
return x&(-x);
}
void dfs(int d,int col,int L,int R){
//d-已放置的棋子个数/行数 col-棋子放置的列信息的状压表示
//L-棋子放置的左倾对角线信息的状压表示 R-棋子放置的右倾对角线信息的状压表示
if(d==n){//已放置n颗棋子
ans++;//方案数增加
return ;
}
//反转状态，将未放置的设为1,放置的设为0
int vis=all&(~(col|L|R|a[d+1]));
for(int i=vis;i;i-=lowbit(i)){//遍历第d+1行所有能放的位置
int x=lowbit(i);//获取具体列的信息
// 下一个棋子 更新列信息 左倾对角线 右倾对角线
dfs(d+1,col+x,(L+x)>>1,(R+x)<<1);
}
}
int main()
{
char c;
cin>>n;
all=(1<<n)-1;//构造二进制n位都为1的数字
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>c;
if(c=='.'){
a[i]|=(1<<(j-1));//将位置信息进行状压
}
}
}
dfs(0,0,0,0);
cout<<ans;
return 0;
}