状态压缩 N皇后问题 —— ylxmf2005的OI教程

N 皇后问题是一个经典的问题,这次我们讲的是如何通过状压挑战难度增加的 N 皇后问题。


在讲这道题之前,我们先讲一下 $N$ 皇后问题。

$N$ 皇后问题

题目

在 $N \times N$ 的方格棋盘放置 $N$ 个皇后,使得它们不相互攻击(即任意 $2$ 个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成 $45^\circ$ 角的斜线上)。
你的任务是,对于给定的 $N$,求出有多少种合法的放置方法。

定义

  1. $row$ 皇后对其所在列的攻击,0表示所在列是安全的,1反之。
  2. $left$ 皇后对其自左上角向右下的主对角线上的攻击,0表示所在主对角线是安全的,1反之。
  3. $right$ 皇后对其自右上角向左下的副对角线上的攻击,0表示所在副对角线是安全的,1反之。
  4. $free$ 综合上三种情况,所有列的情况,1表示所在列是安全的,0反之。
  5. $first$ 从前往后,第一个安全的列,只有一个 1 表示安全,其余都是 0

注意:$row,left,right$ 都是 $0$ 表示当前列安全(空闲)且都是递归的参数,而 $free,first$ 都是 $1$ 表示当前列能够放皇后,是在递归中的临时变量。

$(1<<n)-1$

左移的开始开始只有一个 $1$,设 $n=8$,为 100000000,然后减 $1$,借位,为 11111111。$(1<<n)-1$ 经常表示最大状态。

递归边界

所有列危险即 $row$ 都是 1,所以当 $row=(1<<n)-1$,回溯。

$free$

  1. 如果 $row,left,right$ 中任意个对第 $i$ 列攻击,那么第 $i$ 列危险即为 1

  2. 因为要做到一个为真结果为真,所以用 $row|left|right$,并取反$\sim row| left|right$,第 $i$ 个安全即为 1。但是,取反得到的答案是负数,所以 $free = ((1<<n)-1)\&(\sim row|left|right)$。

注意:取反一定要小心使用。对无符号数 $n$ 取反得到的是 $-(n+1)$,可以通过与上 $(1<>1$。

  1. $right$ 进入下一层递归的方法可参照 $left$ 进入下一层递归的方法,把右移改成左移即可。为$(right|last)<<1$。

代码

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int INF;
void dfs(int row,int left,int right)
{
    if(row==INF)
    {
        ans++;
        return ;
    }
    int free=INF&~(row|left|right);
    while(free)
    {
        int last=free&((~free)+1);
        free&=~last;
        dfs(row|last,(left|last)>>1,(right|last)<<1);
    }
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        INF=(1<<n)-1; ans=0;
        dfs(0,0,0);
        printf("%d\n",ans);
    } 
    return 0;
}

进阶 还是 $N$ 皇后

题目

有一个 $N \times N$ 的方格棋盘,有的位置是 *,表示能放置皇后;有的位置是.,表示不能放置皇后。需要放置 $N$ 个皇后,使得它们不相互攻击(即任意 $2$ 个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成 $45^\circ$ 角的斜线上)。
你的任务是,对于给定的 $N$,求出有多少种合法的放置方法。数据保证有解。

题解

还是 $N$ 皇后与 $N$ 皇后问题的最大不同在于还是 $N$ 皇后会限制某几个方格不能放置皇后。

在输入的棋盘中,用 $a_i$ 表示第 $i$ 行的每一列是否可以放置皇后。如何在输入的时候预处理呢?在 $(i,j)$ 读入到 . 时,需要将 $a_i$ 的第 $j$ 位变成 $1$,为 $a_i|=(1<<(j-1))$。在搜索中,新增一个参数 $lev$ 表示当前搜索至第 $lev$ 行,然后将int free=INF&~(row|left|right);修改成int free=INF&~(row|left|right|a[lev]);即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,ans,INF;
int a[101];
char s[101];
void dfs(int row,int left,int right,int lev)
{
    if(row==INF)
    {
        ans++;
        return ;
    }
    int free=INF&~(row|left|right|a[lev]);
    while(free)
    {
        int last=free&((~free)+1);
        free&=~last;
        dfs(row|last,(left|last)>>1,(right|last)<<1,lev+1);
    }
}
int main()
{
    scanf("%d",&n); INF=(1<<n)-1;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s); 
        for(int j=0;j<n;j++)
            if(s[j]=='.') a[i]|=(1<<j);
    }
    dfs(0,0,0,1);
    printf("%d\n",ans);
    return 0;
}

© ylxmf2005
All rights reserved.
本文不遵从 CC BY-SA 4.0 协议,转载请联系作者。

点赞
  1. liyifenhoi说道:

    沙发

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据