美文网首页
皇后问题

皇后问题

作者: tysnd | 来源:发表于2019-01-19 12:26 被阅读0次

经常做算法赛题的朋友们都知道,八皇后问题是一道经典的搜索回溯题。简单来说,皇后问题就是在一个国际象棋棋盘上摆放若干枚皇后,使得这些皇后无法互相攻击,求出方案数,方案等。而摆放的皇后个数,对位置进行限制,以及要求求出的答案提供了很多变题。最近在洛谷上做到了三题皇后问题,八皇后,K皇后和N皇后。下面介绍一下我对这三题的理解。

一、八皇后
题目链接 https://www.luogu.org/problemnew/show/P1219
分析:这是并不是一道最经典的八皇后问题,有少许变形,不过依然可以采用最普通的深搜加回溯。需要注意的是,由于皇后可以攻击同一行,同一列以及同一对角线上的棋子,因此为了缩减时间复杂度,我们必须找到方法判断棋子是否在同行同列同对角线。也就是说,我们必须找到一些哈希函数,使得我们能在O(1)时间判断两个格子是否在同行同列同对角线。
相关哈希函数:
同行同列很容易判断,对于(x,y)和(i,j)两个格子,x==i和y==j即可判断是否同行同列。而对于主对角线(左上角到右下角的对角线),我们可以看出,若x-y==i-j,则两点在同一主对角线。对于副对角线,若x+y==i+j,则两点在同一副对角线。
深搜和回溯:
对于N*N的棋盘,在深搜的时候,我们可以逐行放皇后,遍历每个点,判断是否可以放皇后,若放到了N个,则找到一种方案。下面贴出AC代码

#include<iostream>
#include<string>
#include<set>
using namespace std;
int N;
int ansnum;
int row[15];
int col[15];
int zd[30];
int fd[30];
int load[15];
set<string> ans;
void dfs(int depth);
bool judge(int x,int y); 
int main()
{
    cin>>N;
    dfs(1);
    int cnt=0;
    for(auto it=ans.begin();it!=ans.end();it++,cnt++)
    {
        if(cnt==3)  break;
        string temp=*it;
        for(int i=0;i<temp.size();i++)
        {
            if(temp[i]>'9'||temp[i]<'0')
                cout<<(int)temp[i]-'a'<<" ";
            else
                cout<<temp[i]<<" ";
        }
        cout<<endl;
    }
    cout<<ansnum<<endl;
    return 0;
}
void dfs(int depth)
{
    if(depth>N)
    {
        ansnum++;
        string res="";
        for(int i=1;i<=N;i++)
        {
            if(load[i]>=10)
                res+=load[i]+'a';
            else
                res+=load[i]+'0';
        }
        ans.insert(res);
        return;
    }
    for(int i=1;i<=N;i++)
    {
        if(judge(depth,i))
        {
            load[depth]=i;
            row[depth]=1;
            col[i]=1;
            zd[depth-i+15]=1;
            fd[depth+i]=1;
            dfs(depth+1);
//回溯
            row[depth]=0;
            col[i]=0;
            zd[depth-i+15]=0;
            fd[depth+i]=0;
        }
    }
}
bool judge(int x,int y)//判断(x,y)是否可以放皇后
{
    return (!row[x]&&!col[y]&&!zd[x-y+15]&&!fd[x+y]);
}

二、K皇后
题目链接 https://www.luogu.org/problemnew/show/P2105
分析:这一题棋盘变成了n*m的矩形,皇后个数变成了K个。不过最大的变化是给出了K个皇后的坐标,并且着K个皇后并非不能互相攻击,而且要求的问题是摆放K个皇后后,棋盘上不能被攻击的格子数。这样,这题其实用不到深搜了。那么暴力的做法是什么呢,将这k个皇后的坐标哈希,然后双重循环,判断每个格子是否被攻击,得答案,复杂度为O(nm)。不过n,m的范围为(1,20000),因此这样显然是tle的。但k的范围是(1,500),因此我的做法是,每放置一个皇后,求出它可以攻击的格子数(注意重复),这样复杂度为O(kn),有了不小的优化。
下面贴出AC代码

#include<iostream>
using namespace std;
int row[20010];
int col[20010];
int zd[40010];
int fd[40010];
int n,m,k;
int inval;
bool judge(int x,int y);
int main() 
{
    cin>>n>>m>>k;
    for(int cnt=0;cnt<k;cnt++)
    {
        int x,y;
        cin>>x>>y;
        //遍历行 
        for(int i=1;i<=m;i++) 
        {
            if(judge(x,i))
                inval++;
        }
        //遍历列 
        for(int i=1;i<=n;i++)
        {
            if(judge(i,y))
                inval++;
        }
        //遍历主对角线 
        for(int i=x-min(x,y)+1,j=y-min(x,y)+1;i<=n&&j<=m;i++,j++)
        {
            if(judge(i,j))
                inval++;
        }
        //遍历副对角线 
        for(int i=x+min(y-1,n-x),j=y-min(y-1,n-x);i>=1&&j<=m;i--,j++)
        {
            if(judge(i,j))
                inval++;
        }
        //若(x,y)在放置皇后前不能被攻击,则多算了三次,要减去 
        if(judge(x,y))
            inval-=3;
        row[x]++;
        col[y]++;
        zd[x-y+20001]++;
        fd[x+y]++;
    }
    cout<<n*m-inval<<endl;
    return 0;
}
bool judge(int x,int y)
{
    return (!row[x]&&!col[y]&&!zd[x-y+20001]&&!fd[x+y]);
}

三、N皇后问题
题目链接 https://www.luogu.org/problemnew/show/P1562
注:本题我并未AC,仅分析一下题解中一位大佬的做法,题解链接 https://www.luogu.org/problemnew/solution/P1562,作者为karma。
分析:
由于这一题和第一题类似,不过添加了一个限制条件,棋盘中一些点不能放皇后,而且数据范围比第一题大1,所以普通的深搜回溯是会tle的。因此我看了karma这位作者的题解,由于他介绍的不太详细,所以我补充一下我的理解。
这一题,题解中使用了状态压缩。
1.dfs中四个参数:now是当前行的状态,ld为副对角线,rd为主对角线,sta[d]为行d的初始状态。
2.四个宏:
xianzhi 得到当前行可以放皇后的位置,由于是0表示可以放,1表示不可以放,所以将四个参数或,为0的位置即为可以放,而在更新状态时需要1为可以放,所以再取反即可。
lowbit 得到当前状态坐标最小的可以放皇后的坐标值,即最右侧1的位置
youzuo 更新主对角线的状态,由于同一对角线上放了一个皇后后其他格子均不能放,而由于是逐行放皇后,当进入下一行时,副对角线与下一行相交的那个格子也不可以放,因为副对角线行坐标加1,列坐标减1,所以要左移1
zuoyou 同理youzuo
其余地方均较容易理解,不再赘述。

以上就是这我对三个皇后问题的理解。总而言之,皇后问题的精髓就是判断是否同行同列同对角线的哈希函数。在理解这个的基础上,再结合相关问题的相关条件,仔细分析思考,相关的变题也就可以做出来了。

相关文章

  • 八皇后问题(N皇后问题)

    八皇后问题是一个经典的递归回溯问题。 描述 八皇后问题是在一个 8*8 的棋盘上放置皇后,要求其放置后满足同一行,...

  • 皇后问题

    经常做算法赛题的朋友们都知道,八皇后问题是一道经典的搜索回溯题。简单来说,皇后问题就是在一个国际象棋棋盘上摆放若干...

  • 【算法】用回溯法(backtracking algorithm)

    什么是N-皇后问题? 说到这个N-皇后问题,就不得不先提一下这个历史上著名的8皇后问题啦。 八皇后问题,是一个古老...

  • N皇后问题(附带JavaScript源代码)

    什么是N-皇后问题? 说到这个N-皇后问题,就不得不先提一下这个历史上著名的8皇后问题啦。 八皇后问题,是一个古老...

  • 回溯之N皇后

    N皇后问题:在 n x n 的棋盘上放置 N 个皇后,使其不能相互攻击。 1. 问题分析 皇后相互攻击是指:在皇后...

  • 八皇后(N皇后问题)

    详解以后慢慢补,看心情。。。 下面这个是有注释的,慢慢列举理解吧~~ 之前不知道看到哪位博主的,我觉得很可以

  • 风云的ARTS打卡(第四周)

    第4周 Algorithm: N皇后问题 n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上,并且使皇后彼此之间...

  • 算法(03)回溯

    八皇后问题

  • N皇后问题

    N皇后问题

  • 第16章 抽象深度优先搜索

    1、2n皇后问题 算法分析 与n皇后问题类似,如下是n皇后问题的分析,时间复杂度 按行继续比遍历,其中col[x]...

网友评论

      本文标题:皇后问题

      本文链接:https://www.haomeiwen.com/subject/jkbadqtx.html