干货|用回溯法(backtracking algorithm)求解N皇后问题(N-Queens puzzle),附代码及详细注释

谈天说地吹个水

哈喽哈喽 ~~ 各位小伙伴好久不见的啦,也不知道大家有没有想我了。如果没有,那我待会再来问一下好了。

嘛,这个时候。想必各位小伙伴早已忘记被考试周支配的恐惧,早就卷好铺盖屁颠屁颠跑回家探(tang)亲(shi)了。小编在这里本着“一天不装逼,浑身难受”的原则。赶在过年前给大家再送上一点干货吧

~~~~~~~~~~~~~~~~

(敲黑板~敲黑板)

接下来我们就要说重点啦。

今天给大家带来嘛好玩的东西呢?

唔……呃……

那自然是大名鼎鼎的

N-皇后问题(N-Queens puzzle)

下面跟随小编的脚步

一起踏入学习的殿堂吧 啦啦啦啦啦啦

内容提要:

回溯算法

定义

基本思想

深度优先搜索

解决问题的步骤

解空间和解空间树

算法框架

皇后问题解决

算法伪代码描述

图解问题过程

coding time

01. 什么是N皇后问题?

什么是N皇后?能吃吗?

哎……不知道嘛?没关系,让小编慢慢道来。说到这个N-皇后问题,就不得不先提一下这个历史上著名的8皇后问题啦。

八皇后问题,是一个古老而著名的问题.该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法?

那么,我们将8皇后问题推广一下,就可以得到我们的N皇后问题了。

N皇后问题是一个经典的问题,在一个N*N的棋盘上放置N个皇后,使其不能互相攻击。(同一行、同一列、同一斜线上的皇后都会自动攻击)那么问,有多少种摆法?

02. 回溯算法

想必各位小伙伴在看完上面的问题以后,写代码的双手早已按耐不住并跃跃欲试了。呃……各位优秀的大学生们请先停下来,装逼的机会多得是……

俗话说那啥工欲善其事必先利其器。N皇后问题其实就是回溯算法中的一个典型应用。为此,在这里小编有必要给大家科普一下回溯算法,顺便感受一下回溯大法好究竟是有多么的给力。

2.1. 回溯算法的定义

回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。(参考自百科)

2.2. 回溯算法的基本思想

回溯算法的基本思想是:

从一条路往前走,能进则进,不能进则退回来,换一条路再试。在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根节点出发深度探索解空间树。当探索到某一节点时,要先判断该节点是否包含问题的解,如果包含,就从该节点出发继续探索下去,如果该节点不包含问题的解,则逐层向其祖先节点回溯。

值得注意的两点

* 若用回溯法求问题的所有解时,要回溯到根,且根节点的所有可行的子树都要已被搜索遍才结束。

* 而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。

2.3. 什么是深度优先搜索?

深度优先搜索(DFS即Depth First Search)其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。

2.4. 回溯法解决问题的一般步骤

1) 针对所给问题,定义问题的解空间,它至少包含问题的一个(最优)解。

2) 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。

3) 以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。

确定了解空间的组织结构后,回溯法就从开始节点(根节点)出发,以深度优先的方式搜索整个解空间。这个开始节点就成为一个活节点,同时也成为当前的扩展节点。在当前的扩展节点处,搜索向纵深方向移至一个新节点。这个新节点就成为一个新的活节点,并成为当前扩展节点。如果在当前的扩展节点处不能再向纵深方向移动,则当前扩展节点就成为死节点。此时,应往回移动(回溯)至最近的一个活节点处,并使这个活节点成为当前的扩展节点。回溯法即以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已没有活节点时为止。

在这里还有必要为大家科普一下解空间和解空间树的知识。

2.5. 解空间和解空间树

1) 解空间

一个复杂问题的解决往往由多部分构成,那么,一个大的解决方案就可以看成是由若干个小的决策组成。很多时候它们构成一个决策序列。解决一个问题的所有可能的决策序列构成该问题的解空间。解空间中满足约束条件的决策序列称为可行解。一般说来,解任何问题都有一个目标,在约束条件下使目标值达到最大(或最小)的可行解称为该问题的最优解。在解空间中,前k项决策已经取定的所有决策序列之集,称为k定子解空间。0定子解空间即是该问题的解空间。这个空间必须至少包含一个解(可能是最优的)。

2) 解空间树

因为回溯方法的基本思想是通过搜索解空间来找到问题所要求的解,所以如何组织解空间的结构会直接影响对问题的求解效率。一般地,我们可以用一棵树来描述解空间,并称之为解空间树。

2.6. 算法框架

1) 递归的算法框架

2) 非递归的算法框架

03. N皇后问题的solve

相信看完上面一大串的回溯算法。各位都已经被科普得想原地爆炸了。好啦,接下来我们就看看如何用回溯的思想解决这个N皇后问题。

3.1算法伪代码描述

下面是算法的高级伪码描述,这里用一个N*N的矩阵来存储棋盘:

1) 算法开始, 清空棋盘,当前行设为第一行,当前列设为第一列

2) 在当前行,当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后),若不满足,跳到第4步

3) 在当前位置上满足条件的情形:

a)在当前位置放一个皇后,若当前行是最后一行,记录一个解;

b)若当前行不是最后一行,当前行设为下一行, 当前列设为当前行的第一个待测位置;

c)若当前行是最后一行,当前列不是最后一列,当前列设为下一列;

d)若当前行是最后一行,当前列是最后一列,回溯,即清空当前行及以下各行的棋盘,然后,当前行设为上一行,当前列设为当前行的下一个待测位置。

e)以上返回到第2步。

4) 在当前位置上不满足条件的情形:

a)若当前列不是最后一列,当前列设为下一列,返回到第2步;

b)若当前列是最后一列了,回溯,即,若当前行已经是第一行了,算法退出,否则,清空当前行及以下各行的棋盘,然后,当前行设为上一行,当前列设为当前行的下一个待测位置,返回到第2步;

3.2图解问题过程

结合图片,相信大家已经够明白了。

3.3 coding time

老铁们,终于到了踏马的激动人心的写代码时间了。

我们之前说过N皇后问题是回溯算法的经典应用。因此我们可以使用回溯法来解决该问题,具体实现也有两个途径,递归和非递归。

3.3.1递归法

其实递归法算是比较简单的了。我们使用一个一维数组来存储棋盘。

具体细节如下:

把棋盘存储为一个一维数组a[N],数组中第i个元素的值代表第i行的皇后位置。

在判断是否冲突时也很简单:

1)首先每行只有一个皇后,且在数组中只占据一个元素的位置,行冲突就不存在了。

2) 其次是列冲突,判断一下是否有a[i]与当前要放置皇后的列j相等即可。

3)至于斜线冲突,通过观察可以发现所有在斜线上冲突的皇后的位置都有规律。即它们所在的行列互减的绝对值相等,即| row – i | = | col – a[i] | 。

代码如下:标注得够明白的啦。如果还看不懂。请自费买豆腐吧

【代码下载移步原文链接】

3.3.2迭代法

为什么还要迭代呢?因为递归效率太低了咯……

具体思路:

首先对N行中的每一行进行探测,查找该行中可以放皇后的位置。具体怎么做呢?

1)首先对该行的逐列进行探测,看是否可以放置皇后,如果可以,则在该列放置一个皇后,然后继续探测下一行的皇后位置。

2)如果已经探测完所有的列都没有找到可以放置皇后的列,这时候就应该回溯了,把上一行皇后的位置往后移一列。

3)如果上一行皇后移动后也找不到位置,则继续回溯直至某一行找到皇后的位置或回溯到第一行,如果第一行皇后也无法找到可以放置皇后的位置,则说明已经找到所有的解,程序终止。

4)如果该行已经是最后一行,则探测完该行后,如果找到放置皇后的位置,则说明找到一个结果,打印出来。

5)但是此时并不能在此处结束程序,因为我们要找的是所有N皇后问题所有的解,此时应该清除该行的皇后,从当前放置皇后列数的下一列继续探测。

由此可见,非递归方法的一个重要问题时何时回溯及如何回溯的问题。

好啦!跟随小编的脚步一起来看看代码吧。【代码下载移步原文链接】

1

END

1

哇,终于写完了。这次的信息量还真有点大呢。大家好好学习好好看哈~~~争取早日修成正果,装的一手好逼。噗~

PS:部分资料参考自网络。

-The End-

文案 / 邓发珩(大一)

排版 / 邓发珩(大一)

指导老师 / 秦时明岳

如对文中内容有疑问,欢迎交流。

邓发珩(华中科技大学管理学院本科一年级、2638512393@qq.com、个人公众号:程序猿声)

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2018-01-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏沈唁志

PHP使用递归算法查找子集获取无限极分类等实操

递归函数是我们常用到的一类函数,最基本的特点是在函数或子过程的内部,直接或者间接地调用自己的算法,但必须在调用自身前有条件判断,否则无限调用下去,也就是所谓的死...

2383
来自专栏蜉蝣禅修之道

网络流算法Push-relabel的Python实现

3705
来自专栏互联网杂技

算法复杂度分析

为什么要进行算法分析? 预测算法所需的资源 计算时间(CPU 消耗) 内存空间(RAM 消耗) 通信时间(带宽消耗) 预测算法的运行时间 在给定输入规模时,所执...

4307
来自专栏用户2442861的专栏

2014美团网笔试题目(总结)

http://blog.csdn.net/wzy_1988/article/details/12438143

1841
来自专栏WindCoder

最大流量和线性分配问题

这里有一个问题:你的业务分配给承包商来履行合同。您可以浏览您的名单,并决定哪些承包商可以参与一个月的合同,你可以查看你的合同,看看哪些合同是一个月的任务。鉴于你...

2552
来自专栏祝威廉

从DataFrame自动化特征抽取的尝试

虽然提供了很多Estimator/Transformer, 正如这篇文章所显示的,如何基于SDL+TensorFlow/SK-Learn开发NLP程序,处理的代...

833
来自专栏深度学习自然语言处理

【笔记】高效率但却没用过的一些numpy函数

最近在看源码的时候,碰到了一些大佬们常用,但自己暂时还没用过的numpy函数,特意来总结下。

672
来自专栏数据结构与算法

BZOJ4484: [Jsoi2015]最小表示(拓扑排序乱搞+bitset)

Description 【故事背景】 还记得去年JYY所研究的强连通分量的问题吗?去年的题目里,JYY研究了对于有向图的“加边”问题。对于图论有着强烈兴趣的J...

36610
来自专栏数据小魔方

sparklines迷你图系列15——Composition(BoxPlot)

今天要跟大家分享的是sparklines迷你图系列14——BoxPlot。 箱线图是用于呈现数据分布形态(功能类似直方图)的一种图表,对于连续型数据,箱线图可以...

3004
来自专栏算法修养

矩阵快速幂小结

      矩阵快速幂大概是用来解决这样一类问题,当你知道了一个递推式比如a[n]=a[n-1]+a[n-2] 题目要求你求出a[n]。如果n大于1亿怎么办? ...

3175

扫码关注云+社区

领取腾讯云代金券