＜算法学习＞回溯——n皇后问题_r回溯法n皇后

目录

原始n皇后问题

问题描述

问题分析

问题求解

n皇后问题变形

问题描述

问题分析

问题解决

---

初学回溯算法时遇到的一个问题。

原始n皇后问题

这个问题的基础版本如下：

问题描述

nxn的棋盘放置n个皇后，要求彼此不能攻击，即同行、同列or同一斜线上不能放两个皇后。求总共有几种放置方案？

问题分析

这个问题是一个典型的回溯问题。我们可以把选择皇后的过程看成树。比如对于4×4的棋盘，第一行有四个位置可以放置皇后，即树的第一层（假设根节点看做第0层）有4个结点。同理，第二行也有四个位置，那么对于树的第一层的每一个结点都会有四个结点分支，以此类推。

按照这种思想，其实我们只需要遍历所有叶子结点对应的路径，判断其是否符合皇后不相互攻击的要求即可。

但是显然我们也可以发现，这种算法效率太低。所以我们需要对某位置是否要放置皇后做一些约束（即回溯算法中的约束条件）。为了进一步优化算法，我们也可以考虑加入剪枝操作（即提前判断某一种路径不符合要求而舍弃）。

问题求解

由以上分析我们就可以试图建立完整算法步骤了。

首先，我们考虑main函数的写法。

我们需要两个变量，一个是n，一个是方案数sum。考虑到有回溯函数的调用，我们把它们设成全局变量，就不用每次都传参了。

我们希望通过调用回溯函数backtrace（）得到结果并输出。

还需要一个数组lie[ ]用于存放每行皇后都放置在哪一列了。

代码如下：

#include <iostream>
using namespace std;
 
int n,sum=0;//sum为放置方法总数
int lie[10];//实际上是需要的是lie[n]，存放每行皇后放置在哪一列了
 
int main()
{
    cin>>n;
    backtrace(//可能有某些参数);
    cout<<sum<<endl;
    return 0;
}

接下来我们考虑backtrace函数的具体实现

首先，对于一个回溯函数，基本结构是一定的。套路如下：

void backtrace(//参数)
{
    if(//终止条件)
    {
        //可能还有某些操作
        return;
    }
    if(//此处可以添加剪枝操作)
    {
        return;
    }
    
    for(//此处循环次数一般为本层所包含的分支结点个数)
    {
        if(//满足约束条件)
        {
            //选择操作--后继续调用回溯函数（记得改参数）
            //选择不操作--后继续调用回溯函数（改的参数个数一般少于上一条）
            //如果有除调用回溯函数之外的操作要撤销
        }
        else
        {
            //不操作--后继续调用回溯函数
        }
    }
}

对于这道题，我们应用上面的套路解答如下

void backtrace(int layer)//layer表示层数，即遍历到棋盘的第几行
{
    if(layer==n) //注意，这里若layer从0开始，条件则为layer==n
                          //若layer从1开始，条件则为layer>n
    {
        sum++;//每次走到这一步就说明已遍历完所有的行（即放完所有皇后）
              //则符合要求的解法数++
        return;
    }
    
    //未添加剪枝操作
 
    for(int i=0;i<n;i++)//遍历当前行所有列，i表示当前列数
    {
 
        int flag=1;//标志量为1代表可以放置
        for(int j=0;j<layer,j++)//遍历之前的行上放置过的皇后
        {
            if(i==lie[j]||abs(i=lie[j])==layer-j)//若和之前行的皇后同列或同对角线则不放
            {
                flag=0;
                break;
            }
        }
 
        if(flag==1)  //若当前位置能放
        {
            lie[layer]=i;//则在该列放置皇后
            backtrace(layer+1);//继续遍历下一行
        }
    }
}

与套路中的过程相比，我们发现，解法中的第一层循环实际表示的正是当前结点分支输，而第二层循环实际属于约束条件的构造过程。 而if(flag==1)恰是约束条件的判断。所以这个解题方法是完全符合回溯法的一般解题套路的。

我们还发现这个解法中没有“不放”的操作。也就是能放就放，不能放好像没说咋办就过去了。

实际上我们跟着代码的流程走一遍就会发现，不能放的话，这一层的backtrace函数会结束，返回上一层的backtrace函数，也就是说会从上一层的layer继续遍历列数，寻求上一层皇后新的放置方法。而这正是我们想要的。

到此为止原始的n皇后问题就结束了。（根据所需合并代码并添加所需头文件即可）

n皇后问题变形

问题描述

我们对八皇后问题进行扩展。

国际象棋中的皇后非常神勇，一个皇后可以控制横、竖、斜线等4个方向（或者说是8个方向），只要有棋子落入她的势力范围，则必死无疑，所以对方的每个棋子都要小心地躲开皇后的势力范围，选择一个合适的位置放置。如果在棋盘上有两个皇后，则新皇后控制的势力范围与第一个皇后控制的势力范围可以进行叠加，这样随着皇后数量的增加，皇后们控制的范围越来越大，直至控制了棋盘中全部的格子。

现在我们关心的是，如果在 N×N 的棋盘上放入 M 个皇后（M个皇后相互之间不能冲突）控制棋盘中的格子，则共有多少种不同的放置方法？

输入：
     N (N <= 10)  M (M < N)

输出：
    如果将 M 个皇后放入 N×N 的棋盘中可以控制全部棋盘中的格子，则不同的放置方法的数量

问题分析

这个问题跟原始的n皇后问题的不同之处有两点：

1、可能不是每一行都有皇后。

2、顺利放置完皇后还没结束，还要判断是否所有格子都在控制范围之内。若满足要求才能增加方案数。

解决这两个问题也很简单：

1、根据回溯法套路，加上选择放或不放的操作。（而不是能放就放，不能放等函数自动回退）

2、增加一个判断函数，判断是否所有格子都在控制范围之内。

问题解决

根据以上分析，我们尝试构建代码。

首先写首部代码

#include <bits/stdc++.h>
using namespace std;
#define MAX 15
#define MM 30
int res=0;//方案数
int N,M; //N×N的棋盘和 M个皇后
int hang[15],lie[15];//存放皇后放置位置行、列的数组
int xie1[33],xie2[33];//记录每条斜行是否有皇后控制的标志量

再考虑main函数

int main()
{
    cin>>N>>M;
 
    memset(hang,-1,sizeof(hang));  //初始化
    memset(lie,-1,sizeof(lie));
    memset(xie1,-1,sizeof(xie1));
    memset(xie2,-1,sizeof(xie2));
 
    backt(0,1,0);
    backt(1,1,1);
 
    cout<<res<<endl;
    return 0;
}

 再看判断格子是否被完全控制的函数

int judge()
{
    for(int i=1;i<=N;i++) //遍历所有行
    {
        if(hang[i]==-1)//如果当前行没被控制
        {
            for(int j=1;j<=N;j++) //遍历所有列
            {
                if(lie[j]==-1)  //如果当前列没被控制
                {
                    if(xie1[i+j]==-1&&xie2[N+i-j+1]==-1) //如果当前正反斜线也没被控制
                    {
                        return 0; //说明有格子没被控制，不符合要求，返回0
                    }
                }
            }
        }
    }
    return 1;  //符合要求，返回1
}

关于正反斜线的公式大家可以找一下格子横纵坐标的规律。

一条斜线的横纵坐标相加为定值，一条斜线的横纵坐标相减为定值。

还要注意每种斜线有2N-1条（比如4×4的棋盘，有7条正斜线7条反斜线，若i，j均从0开始，则编号分别为0到6和2到8）

最后来看回溯函数

void backt(int flag,int layer,int now) //flag用于决定layer层是否放皇后
{
    if(layer>N)  //layer从1开始，所以终止条件是>N
    {
        if(now==M)
        {
            int ff=judge(); //到终止层之后还需判断棋盘格子是否全部被控制
            if(ff)
            {
                res++; //全部被控制才能+方案数
                return;
            } 
        }
        else return;
    }
    else
    {
        if(now+N-layer<M) return;//剪枝（如果还没遍历到的所有行都放皇后，加上现在已经放了的皇后数还比M小，不必往下遍历，该方案直接pass）
        if(flag==0)  //如果该行不放皇后，直接进入下一行
        {
            backt(0,layer+1,now);  //决定下一行放皇后
            backt(1,layer+1,now+1); //决定下一行不放皇后
        }
        else  //如果该行被决定放皇后
        {
            for(int i=1;i<=N;i++)  //i代表列，遍历当前行的每一列
            {
                if(hang[layer]==-1&&lie[i]==-1&&xie1[layer+i]==-1&&xie2[N+layer-i+1]==-1)
                {  //约束条件：行、列、对角线都不能被其他皇后控制
                    
                    //在该列选择放
                    lie[i]=i;     //放完后更新刚放的这个皇后的控制区域标记
                    hang[layer]=layer;
                    xie1[layer+i]=1;
                    xie2[N+layer-i+1]=1;
                    
                    //进入下一行回溯
                    backt(0,layer+1,now);  //决定下一行放皇后
                    backt(1,layer+1,now+1);  //决定下一行不放皇后
 
                    //在该列选择不放
                    lie[i]=-1;  //撤销除回溯函数外的其他相关操作
                    hang[layer]=-1;
                    xie1[layer+i]=-1;
                    xie2[N+layer-i+1]=-1;
                }
                
            }
 
        }
    }
}

可以发现上述解法其实是符合套路的。

而预先决定layer层放不放的标志量flag其实也起到了回溯的作用，也就是说相当于替代了双重循环中的外层循环。