递归之N皇后问题

Kubrnete 等级 369 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://blog.csdn.net/guanguandaren/article/details/115242535,如有侵权,请联系删除。

收藏
评论区

相关推荐

Java实现排序算法
//冒泡排序 public static void bubbleSort(int data) { int n data.length; for (int i 0; i < n; i) { for (int j 0; j < n; j) { if (
Swift与Objective-C混合编程之Swift与Objective-C API映射
原创文章,欢迎转载。转载请注明:关东升的博客 Swift与ObjectiveC API映射 在混合编程过程中Swift与ObjectiveC调用是双向的,由于不同语言对于相同API的表述是不同的,他们之间是有某种映射规律的,这种API映射规律主要体现在构造函数和方法两个方面。 1、构造函数映射 在Swift与ObjectiveC语言进行混合
数据库系统概论
一、范式与规范 1.1 一个二元组一定属于BCNF eg: R {A, B, C},{B C, BA } 等价于{B AC} 1.2 求候选码 1. 列出左右出现的元素:L, R, LR,N。(当右边出现组合元素时,拆分开来) 1. 从(L N) 中的元素开始求闭包,能推出所有元素则一定是唯一的候选码。 1. 如果L中的闭包推不出
防抖和节流
防抖 触发高频事件后n秒内函数只会执行一次,如果n秒内高频事件再次触发,则重新计算事件 思路 每次触发的时候取消之前的延时调用方法,以当下为准 //防抖 function debounce(fn){ let timeout null; return function(){ clearTimeout
C 语言代码大全
1 两个数组的合并 题目描述 已知数组a中有m个按升序排列的元素,数组b中有n个按降序排列的元素,编程将a与b中的所有元素按降序存入数组c中。 输入 输入有两行,第一行首先是一个正整数m,然后是m个整数;第二行首先是一个正整数n,然后是n个整数,m, n均小于等于1000000。 输出 输出合并后的mn个整数,数据之间用空格隔开。输出占一行。 样例输入 4
C语言基础习题50例(二)6-10
给大家推荐一门大数据Spark入门课程,希望大家喜欢。 习题6 用 号输出字母C的图案。实现思路:单行打印即可。代码如下:cinclude <stdio.h int main (void){ printf("\n"); printf("\n"); printf("\n"); printf("
递归之N皇后问题
问题描述: N皇后问题是指在N\N的棋盘上要摆N个皇后, 要求:任何两个皇后不同行,不同列也不再同一条斜线上, 求给一个整数N,返回N皇后的摆法数。N皇后问题涉及到回溯的思想。我们通常用递归解决,代码实现会比较简单。递归其实可以看作底层帮我们维护了一个自动push、pop的堆栈。网上也有很多N皇后的相关题解,这篇文章经过我的整理,保
C语言基础习题50例(六)26-30
习题26 利用递归方法求5。实现思路:使用递归。代码如下:cinclude<stdio.hint main(){ int rec(int n); int result rec(5); printf("5 %d\n", result); return 0;}int rec(int n){ if(n 1 || n
python刷题-特殊回文数
问题描述  123321是一个非常特殊的数,它从左边读和从右边读是一样的。  输入一个正整数n, 编程求所有这样的五位和六位十进制数,满足各位数字之和等于n 。 输入格式  输入一行,包含一个正整数n。 输出格式  按从小到大的顺序输出满足条件的整数,每个整数占一行。 样例输入52 样例输出899998989989998899 数据规模和约定 
python刷题-最大最小公倍数
问题描述已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。 输入格式输入一个正整数N。 输出格式输出一个整数,表示你找到的最小公倍数。 样例输入9 样例输出504 数据规模与约定1 < N < 106。 N int(input())Min 1if N<2: print(N)elif N%2
为什么要用 setTimeout 模拟 setInterval ?
在JS 事件循环之宏任务和微任务中讲到过,setInterval 是一个宏任务。 用多了你就会发现它并不是准确无误,极端情况下还会出现一些令人费解的问题。下面我们一一罗列..推入任务队列后的时间不准确定时器代码:setInterval(fn(), N); 上面这句代码的意思其实是fn()将会在 N 秒之后被推入任务队列。所以,在 setInterval
[C#]ArrayList、string、string[]之间的转换
1、ArrarList 转换为 string\[\] :  ArrayList list new ArrayList();  list.Add("aaa");  list.Add("bbb");  string\[\] arrString (string\[\])list.ToArray(typeof( string)) ;2、string\[\] 转换
人工智能数学基础6:无穷大和无穷小的大小比较以及斯特林公式
1.无穷大的大小排列n、a1、a2、a3为自然数(表述为n∈N),n趋于无穷大(n→∞),a1、a2、a3大于1,则下列实数的大小排列为: 2\. 无穷小的大小排列将无穷大的大小排列公式中比较的数字作为分母,1作为分子,大于号改为小于号,则可以作为无穷小大小排列公式: 3.极限值n为自然数(表述为n∈N),n趋于无穷大(n→∞),a2、a3大于1,则
题解5道c++面试题第一期(含解题思路、答案解析和实现代码)
本篇文章送上5道c/c++面试题目,并附上答案、解题思路以及扩展知识。 1. 求下面函数的返回值c++include <stdio.hint func(int x) int iCnt 0; while(x) iCnt++; x x&(x1); return iCnt;int main() printf("cnt %d\n", func(9999
ONNX 开始
环境 基础 bashconda create n onnx python3.8 yconda activate onnx ONNX https://github.com/onnx/onnxconda install c condaforge onnx ypython c "import onnx; print(onnx.version)"pyimport