【题1】n皇后问题

《【题1】n皇后问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

4、态的定义如下varstack：array[1‥4]ofinteger；{stack[i]为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、已处理过的结点若以后不会再用，则不必保留。即回溯过程中经过的结点不再保留。例如在上图中，当我们求出第一种摆法v1－v2－v3后，由于皇后置放第三行任何列位置都会产生攻击，因此舍弃该摆法，开始寻求第二种摆法。从上图可看出，第二条路径为v1－v2－v4－v5，v3在第二种摆法中不再用