递归之N皇后问题

Kubrnete 等级 239 1 0

问题描述:

N皇后问题是指在N*N的棋盘上要摆N个皇后, 要求:任何两个皇后不同行,不同列也不再同一条斜线上, 求给一个整数N,返回N皇后的摆法数。

N皇后问题涉及到回溯的思想。我们通常用递归解决,代码实现会比较简单。递归其实可以看作底层帮我们维护了一个自动push、pop的堆栈。网上也有很多N皇后的相关题解,这篇文章经过我的整理,保证你能看懂。

理解DFS的关键在于解决“当下该如何做”。至于“下一步如何做”则与当下是一样的。

因此,我们在递归的时候,只要关心第一步应该如何开始,以及最后一步何时结束,就能够写出DFS的基本模型。

初步认识DFS

为了方便无基础的读者阅读,顺带写上用DFS求1~n全排列的解法。

如果想直接看N皇后问题,可直接跳转

算法分析:

这里我们可以将全排列模拟成对n个纸条标上数字,所以需要一个长度为n的数组a[n],再用一个数组book记录数字是否已经被使用。当某纸条标上数字i后,则book[i]=1。由于求全排列还需要取出数字重新组合,要重新赋值为0。

第一步:

我们关注的问题是:如何找出一种排列方式?

void dfs(int k)
{
    if (k > n) //n个字条都被标记了
    {
        return; //找完第一种,结束尝试
    }
    for (int i = 1; i <= n; i++) //遍历1~n数字,为纸条标记数字
    {
        if (!book[i]) //如果数字未使用
        {
            a[k] = i; //标上i
            book[i] = 1;
        }
    }
}
第二步:

我们将第一步的处理方法递推到后面的每一步。很容易想到,我们在一个函数中实现第一步,然后通过递归调用这个函数实现解决思路相同的下一步,直到应有的处理方案都试完,就可以结束。这就是DFS。

完整代码
#include <bits/stdc++.h>
using namespace std;
const int n = 3;
int a[n], book[n + 1];
void dfs(int k)
{
    if (k > n) //n个字条都被标记了
    {
        for (int i = 1; i <= n; i++)
            printf("%d", a[i]);
        printf("\n");
        return; //结束第一次尝试
    }
    for (int i = 1; i <= n; i++) //遍历1~n数字,为纸条标记数字
    {
        if (!book[i]) //如果数字未使用
        {
            a[k] = i; //标上i
            book[i] = 1;
            dfs(k + 1); //函数的递归调用(自己调用自己),继续标记第k+1纸条,直到n张纸条都标记完
            book[i] = 0;
            /**
             * 这里之所以要置0,是因为在进入这个代码时,
             * dfs一次调用完成,已经能得到了第一组排列方式
             * 接下来会往前回退求新的排列方式
             * 必须收回原有的标记才能继续做新的尝试
             **/
        }
    }
}

int main()
{
    dfs(1); //k表示现在要标记的是纸条k,从第一个开始
}

N皇后问题

下面我们依照上面的思路解决N皇后问题。首先给出DFS的基本模型,实现过程中会稍作调整。

start:
初始化数组
dfs(k){ 放置第k个皇后
    if(判断边界){ 合法则开始尝试
        for(i=1;i<=n;i++){ 
            尝试每一种可能
            dfs(k+1)   继续下一种尝试
            回溯,恢复状态         
        }
    }
    else{ 放置位置超出棋盘
        完成第一次递归,求解数+1
        返回
    }
}
end
算法分析:
普通DFS:

我们需要一个二维数组当作棋盘。

首先:如何放置第一种摆法?

核心思路是:对走过的每一行,判断当前列的位置是否可放置,然后遍历每一列,就得到第一种摆法

然后从第一行开始试,尝试n次。这就是N皇后的DFS解法。

要判断当前位置的列和对角线是否能放置棋子,

就要对走过的每一行都检查。因此,我们需要这样一个函数

bool check(int row, int col)
{
    /**由于要判断当前位置的列和对角线是否能放置
     * 就要对走过的每一行都检查 **/

    for (int i = 1; i <= row; i++)
    {
        if (g[i][col]) //对每一行检查当前列
            return false;
    }
    for (int i = row - 1, j = col - 1; i > 0 && j > 0; i--, j--)
    {
        if (g[i][j]) //检查左上斜线
            return false;
    }
    for (int i = row - 1, j = col + 1; i > 0 && j <= n; i--, j++)
    {
        if (g[i][j]) //检查右上斜线
            return false;
    }
    return true;
}

纯DFS完整代码为

#include <bits/stdc++.h>
using namespace std;
const int n = 8;
int ans = 0;
int g[n + 1][n + 1];
bool check(int row, int col)
{
    /**由于要判断当前位置的列和对角线是否能放置
     * 就要对走过的每一行都检查 **/

    for (int i = 1; i <= row; i++)
    {
        if (g[i][col]) //对每一行检查当前列
            return false;
    }
    for (int i = row - 1, j = col - 1; i > 0 && j > 0; i--, j--)
    {
        if (g[i][j]) //检查左上斜线
            return false;
    }
    for (int i = row - 1, j = col + 1; i > 0 && j <= n; i--, j++)
    {
        if (g[i][j]) //检查右上斜线
            return false;
    }
    return true;
}
void dfs(int k) //k表示第k行
{
    if (k > n)
    {
        ans++;
        return;
    }
    for (int col = 1; col <= n; col++)
    { //遍历k行的每一列
        if (check(k, col)) //如果该位置可放置
        {
            g[k][col] = 1;
            dfs(k + 1);
            g[k][col] = 0;
        }
    }
}

int main()
{

    dfs(1);
    cout << ans;
}

时间复杂度O(N!),空间复杂度(N^2),下面我们将开始优化。由于我这里只介绍N皇后的递归解法,下面提供的解法主要是在思路上有所改进。

重述一遍思路:对走过的每一行,判断当前列的位置是否可放置,然后遍历每一列,就得到第一种摆法

由于在N皇后规则中,同行同列且同一斜线仅存在1个皇后,那我们能否不用二维数组模拟棋盘呢?

优化1.0:

其实,我们可以用一维数组分别表示列和对角线上的棋子状态,通过直线斜率判断两个棋子是否在同一斜线上。

递归之N皇后问题

由于在这个棋盘中,放置棋子处于同一斜线上的斜率k仅可取1和-1。我们以图上A(x1,y1)和B(x2,y2)两点为例 由直线方程两点式:

$\frac{x-x1}{x2-x1}$=$\frac{y-y1}{y2-y1}$

化简一般式:y = $\frac{y2-y1}{x2-x1}$(x-x1) ,其中,k= $\frac{y2-y1}{x2-x1}$ 。显然,当且仅当$| y2-y1 |$=$|x2-x1|$时,两个棋子位于同一斜线上。在对遍历每列时,当前行就是*y2,当前列就是x2**。

首先,我们将列的值存入以行为下标的数组里,就可以同时表达行与列的关系。核心代码为:

 for (int x2 = 1; x2 <= n; x2++) //对当前行的每列遍历
    {
        g[y2] = x2;
         if(check(y2))dfs(...)   //列的值已经存在g[]里面,找到当前行能够放置的x2
    }

注意:g[]不再表示位置是否已放置,而是表示y2行在哪一列放置了皇后。

这样,我们压缩了棋盘数组的空间。只要对每列遍历,找到当前行能够放置的x2就可以了。

然后加上判断位置是否可放置皇后的函数,就能完成啦。

完整代码如下:

#include <bits/stdc++.h>
using namespace std;
const int n = 8;
int ans = 0;
int g[n + 1]; 
//注意:g[]不再表示某位置是否已放置,而是表示某行在哪一列放置了皇后,简单的说就是下标为行y,值为x的数组
bool check(int y2)
{
    for (int y1 = 1; y1 < y2; y1++)
    {
        if (g[y2] == g[y1] || y2 - y1 == abs(g[y2] - g[y1])) //y2-y1==|x2-x1| (y1<y2)
        /**
         * 1. 检查走过的行中有无同一列放置的皇后
           2. 检查走过的行中有无同一斜线放置的皇后(通过斜率判断)
        */
           return false;
    }
    return true;
}
void dfs(int y2) //y2表示纵坐标为y2,即y2行
{
    if (y2 > n)
    {
        ans++;
        return;
    }
    for (int x2 = 1; x2 <= n; x2++) //对每列遍历,找到当前能够放置的x2
    {
        g[y2] = x2;
        if (check(y2))
        {
            dfs(y2 + 1); //由于一直在对列遍历,无需一次dfs调用完成后恢复数组
        }
    }
}

int main()
{

    dfs(1);
    cout << ans;
}
优化1.1:

我们可以发现,只要知道行和列,对应的斜线位置也知道了。

于是,对前k行的每一列遍历时,只要判断该位置列和主对角线、副对角线能否放置就可以了

递归之N皇后问题 递归之N皇后问题

由上图(转自leetcode),我们将得出两个结论:

  1. 主对角线上,每个位置满足行下标与列下标之差相等
  2. 副对角线上,每个位置满足行下标与列下标之和相等

那么现在,我们y也可以用3个一维数组去维护棋盘的状态。它们分别表示列和主、副对角线。

这就是N皇后问题的常规DFS解法,我们的判断条件可以改为:

 if (!(col[y] || line1[k + y] || line2[n-(k-y)])) //如果该位置可放置

只需要对每列遍历一次,就可以判断该位置是否可放。

注意:由于对主对角线判断时会出现下标之差为负数,又因为对称性,同一棋盘会有两条主对角线行下标与列下标之差的绝对值相等。因此,这里判断的下标应该为n-(k-y) (有点像使数组下标溢出并作不进位处理)

核心代码如下:

void dfs(int k) //k表示第k行
{
    if (k > n)
    {
        ans++;
        return;
    }
    for (int y = 1; y <= n; y++)
    {                                                     
        if (!(col[y] || line1[k + y] || line2[n - (k-y)])) 
        {
            col[y] = line1[k + y] = line2[n - (k-y)] = 1;
            dfs(k + 1);
            col[y] = line1[k + y] = line2[n - (k-y)] = 0;
        }
    }
}
优化2:

完整代码如下

return [1,0,0,2,10,4,40,92,352,724,2680,14200,73712,365596][n-1]

再见(逃 本文转自 https://www.helloworld.net/redirect?target=https://blog.csdn.net/guanguandaren/article/details/115242535,如有侵权,请联系删除。

收藏
评论区