【题1】n皇后问题

《【题1】n皇后问题》由会员分享，可在线阅读，更多相关《【题1】n皇后问题（4页珍藏版）》请在金锄头文库上搜索。

1、【题题 1 1】n n 皇后问题皇后问题 一个（1n100）的国际象棋棋盘上放置个皇后，使其不能相互攻击，即任何两个皇后都 不能处在棋盘的同一行、同一列、同一条斜线上，试问共有多少种摆法？ 输入：输入： n 输出：输出： 所有分案。每个分案为 n+1 行，格式： 方案序号 以下 n 行。其中第 i 行（1in）行为棋盘 i 行中皇后的列位置。在分析算法思路之前，先让我们介绍几个常用的概念： 1、状态（、状态（state）状态是指问题求解过程中每一步的状况。在皇后问题中，皇后所在的行位置 i(1in)即为其时皇 后问题的状态。显然，对问题状态的描述，应与待解决问题的自然特性相似，而且应尽量做到占

2、用空间 少，又易于用算符对状态进行运算。2、算符、算符（operater）算符是把问题从一种状态变换到另一种状态的方法代号。算符通常采用合适的数据来表示，设为局 部变量。n 皇后的一种摆法对应 1 排列方案（a1 ，an ） 。排列中的每个元素 ai 对应行上皇后 的列位置（1in） 。由此想到，在皇后问题中，采用当前行的列位置 i(1in)作为算符是再合适不 过了。由于每行仅放一个皇后，因此行攻击的问题自然不存在了，但在试放当前行的一个皇后时，不是 所有列位置都适用。例如(l，)位置放一个皇后，若与前 1 l-1 行中的 j 行皇后产生对角线攻击 (l=aji)或者列攻击(aj)，那么算符显

3、然是不适用的，应当舍去。因此，不产生对角线 攻击和列攻击是皇后问题的约束条件，即排列（排列 a1，ai，aj，an ）必须满足条件 (ajai) and (aiaj ) (1i，jn)。3、解答树（、解答树（analytic tree） 现在让我们先来观察一个简单的皇后问题。设4，初始状态显然是一个空棋盘。此时第一个皇后开始从第一行第一列位置试放，试放的顺序是从左至右、自上而下。每个棋盘由 个数据表征相应的状态信息（见下图）： （ ） 其中第 i（1i4）个数据指明当前方案中第 i 个皇后置放在第 i 行的列位置。若该数据为，表明所在 行尚未放置皇后。棋盘状态的定义如下varstack：arr

4、ay14of integer； stacki为 i 行皇后的列位置 从初始的空棋盘出发，第个皇后可以分别试放第行的个列位置，扩展出个子结点。在上图中，结点右上方给出按回溯法扩展顺序定义的结点序号。现在我们也可以用相同方法找出这些结点的第二行的可能列位置，如此反复进行，一旦出现新结点的四个数据全非空，那就寻到了一种满足题 意要求的摆法。当尝试了所有可能方案，即获得了问题的解答，于是得到了下列图形。该图形象一棵倒悬的树。其初始结点 v1 叫根结点，而最下端的结点 v3 、v5 、v9 、v13 、v16 、v17 称为 叶结点，其中 2 个数据全非零的叶结点，亦即本题的目标结点。由根结点到每一个目

5、标结点之间，揭示 了一种成功摆法的形成过程。显然，皇后问题存在由 v9 、v13 表示的二种方案。上图被称作解答树。 树中的每一结点都是当前方案中满足约束条件的元素状态。除了根结点、叶结点以外的结点都称作分枝 结点。分枝结点愈接近根结点者，辈分愈高；反之，愈远离根结点者，辈分愈低。上图中结点 v7 是结点 v8 的父结点（又称前件） ，结点 v13是结点 v12的子结点（又称后件） 。某结点所拥有的子结点的个数称作 该结点的次数。显而易见，所有叶结点的次数为。树中各结点次数最大值，被称作为该树的次数。算 符的个数即为结解答树的次数。由上图可见，皇后的解答树是次树。 一棵树中的某个分枝结点也可视

6、作为“子根” ，以该结点为根的树则称作“子树” 。由以上讨论可以 看出解答树的结构： 1、初始状态构成（主）树的根结点。对应于皇后来说，初始时的空棋盘即为根结点； 2、除根结点以外，每个结点都具有一个、且只有一个父结点。对应于皇后问题来说，置放 i 行皇 后的子结点，只有在置放了前 i-1 行皇后的一个父结点基础上产生； 3、每个非根结点都有一条路径通往根结点，其路径长度（代价）定义为这条路径的边数。对应于 皇后来说，当前行序号即为路径代价。当路径代价为 n时，说明 n 个皇后已置放完毕，一种成功的摆 法产生。有了以上的基础知识和对皇后问题的初步分析，我们已经清楚地看到，求解皇后问题，无非就

7、是做两件事：1、从左至右逐条树枝地构造和检查解答树 t；2、检查 t 的结点是否对应问题的目标状态； 上述两件事同时进行。为了加快检查速度，一般规定：1、再扩展一个分枝结点前进行检查，只要它不满足约束条件，则不再构造以它为根的子树； 2、已处理过的结点若以后不会再用，则不必保留。即回溯过程中经过的结点不再保留。例如在上图 中，当我们求出第一种摆法 v1v2v3后，由于皇后置放第三行任何列位置都会产生攻击，因此舍弃该 摆法，开始寻求第二种摆法。从上图可看出，第二条路径为 v1v2v4v5，v3在第二种摆法中不再用到， 不必保留，应当退回到 v2状态，在第二行选择尚未使用过的列位置 4，扩展出 v

8、4。一般来说，当求出一 条路径后，必须从叶结点开始，沿所在路径回溯，回溯至第一个还剩有适用算符的分枝点（亦称为尚未 使用过的通向右边方向的结点） ，从那里换上一个新算符，继续求下一条路径。按上述规定对照上图，我们来具体分析皇后的置放过程。初始状态（，）作为根结 点 v1，由此出发，置第个皇后于第行第列位置。从（，）开始，第个皇后相继选 择了第行的、列位置，由于会产生攻击，因此选择该行的列位置放入，产生状态 （，） 。但是第个皇后无论放入第行哪列位置都难逃攻击，因此只得沿第一条路径回溯 至第一个尚未用过的通向右边方向的分枝点 v2 ，以寻求第二种摆法。从（，）状态换上新的列位置，产生（，） 。从

9、（，）选择列位置（由于列位置产生攻击） ， 产生（，） 。由于第个皇后无论置放第行哪列位置都会产生攻击，第二种摆法失败，同 样再从 v5开始，沿第二条路径回溯。由于 v2，v4都没有未使用的满足约束条件的算符（列位置）了，因 此第一个分枝点是 v1，从 v1的（，）换上位置，产生 v6的（，） 。这样依 次使用满足约束条件的算符扩展下去，又得出第三条路径 v1v6v7v8v9。可见，v9的 （，）是一种成功的摆法。按上述规律不断回溯检查，直至得出第六条路径 v1v14v17。 沿路径从 v17回溯，由于 v14选择尚未用过的列位置、都会产生攻击，因此不再剩有适用的列位置了， 只得回溯至 v1。

10、又因为 v1 已经选择了列位置而无法再扩展，至此，求出了皇后的所有可能摆法。由上述扩展过程引出回溯法的基本思想：从左至右逐条树枝地构造和检查查找解答树，已处理过的从左至右逐条树枝地构造和检查查找解答树，已处理过的 结点若以后不会再使用则不必保留（一般说来，检查长度为结点若以后不会再使用则不必保留（一般说来，检查长度为 n n 的树枝，只要保留的树枝，只要保留 n n 个结点就够了）个结点就够了） 。若按。若按 这种方式得到一条到达树叶的树枝这种方式得到一条到达树叶的树枝 t t，实际上就得到了一条路径。然后沿树枝，实际上就得到了一条路径。然后沿树枝 t t 回溯到第一个尚未使用过回溯到第一个尚

11、未使用过 通往右边路径方向上的分枝点，并由此分枝点向右走一步，然后再从左至右地逐个进行构造和检查，直通往右边路径方向上的分枝点，并由此分枝点向右走一步，然后再从左至右地逐个进行构造和检查，直 至达到叶子为止，这时又得到一条路径。按这种方法搜索下去，直至求出所有路径。显然用这种方法检至达到叶子为止，这时又得到一条路径。按这种方法搜索下去，直至求出所有路径。显然用这种方法检 查，在树枝左边的一切结点都已检查过，树枝右边的一切结点尚未产生出来。我们把这种不断查，在树枝左边的一切结点都已检查过，树枝右边的一切结点尚未产生出来。我们把这种不断“回溯回溯” 查找解答树中目标结点的方法，称作查找解答树中目标

12、结点的方法，称作“回溯法回溯法” 。 由上述算法思想，我们很容易想到，应选择怎样一种数据结构来存放当前路径上各结点的状态和算 符？它应具有“后进先出”的特征，就象食堂里的一叠盘子，每次只许一个一个地往顶上堆，一个一个 地从顶上往下取。这就是我们通常所说的栈。栈是一种线性表，所有进栈或出栈的数据都只能在表的同 一端进行，就象堆盘子和拿盘子一样，都只能在顶端“堆上”或“取下” 。这顶端叫“栈顶” ，另一端叫 “栈底” 。Pascal 编译系统内部，保留一部分内存用作栈区，存放过程和函数的值参以及过程和函数内部 所说明的局部变量。每当一个过程和函数被启用时，系统就在栈顶分配一组值参和局部变量（进栈）

13、 。而 当该过程或函数退出时，这些局部变量或值参就被消除（退栈） 。我们为回溯法设计的一个递归过程 run 就是利用系统的这一特性： procedure run（当前状态） ；var i：integer；beginif 当前状态为边界then beginif 当前状态为最佳目标状态 then 记下最优结果；exit； 回溯end；thenfor i算符最小值 to 算符最大值 dobegin算符 i 作用于当前状态，扩展出一个子状态；if (子状态满足约束条件) and (子状态满足最优性要求)then run(子状态)；end；forend；run 我们在应用回溯法求所有路径的算法框架解题时

14、，应考虑如下几个重要因素： 定义状态：定义状态：即如何描述问题求解过程中每一步的状况。在 n 皇后问题中，将行位置 l 作为状态。如果扩 展结点时参与运算的变量有多个，为了精简程序，增加可读性，我们一般将参与子结点扩展运算的变量 组合成当前状态列入值参，以便回溯时能恢复递归前的状态，重新计算下一条路径； 边界条件：边界条件：即在什么情况下程序不再递归下去。在 n 皇后问题中，将 l=n+1（产生一种成功摆法）作为 边界条件。如果是求满足某个特定条件的一条最佳路径，则当前状态到达边界时并非一定意味着此时就 是最佳目标状态。因此还须增加判别最优目标状态的条件；搜索范围：搜索范围：在当前状态不满足边

15、界条件的情况下，应如何设计算符值的范围。换句话说，如何设定 for 语句中循环变量的初值和终值。在 n 皇后问题中，l 行的列位置 i 作为搜索范围，即 1in；约束条件约束条件 和最优性要求：和最优性要求：所谓约束条件是指，当前扩展出一个子结点后应满足什么条件方可继续递归下去；如果 是求满足某个特定条件的一条最佳路径，那么在扩展出某个子状态后是否继续递归搜索下去，不仅取决 于子状态是否满足约束条件，而且还取决于子状态是否满足最优性要求。在 n 皇后问题中，将(l，i)置放 皇后不产生攻击（att=false）作为约束条件； 参与递归运算的参数：参与递归运算的参数：将参与递归运算的参数设为递归子程序的值参或局部变量。若这些参数的存储 量大（例如数组）且初始值需由主程序传入，为避免内存溢出，则必须将其设为全局变量，且回溯前需 恢复其递归前的值。在 n 皇后问题中，将皇后的行位置 l 和列位置 i 作为参与递归运算的参数；虽然上述程序流程仅是一种“粗线素描” ，但其编排直接面对问题，囊括回溯搜索的所有本质特征， 并有意识地在问题与算法之间显现一种“隐约可见”的思维自由度，