还是 N 皇后

题目描述

正如题目所说，这题是著名的 $N$ 皇后问题。

输入格式

第一行有一个 $N$。接下来有 $N$ 行 $N$ 列描述一个棋盘，* 表示可放，. 表示不可放。

输出格式

输出方案总数。

样例 #1

样例输入 #1

4
**.*
****
****
****

样例输出 #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;
}

还是N皇后