数据结构课程设计回溯法解决8皇后n皇后问题.doc

数据结构课程设计 回溯法解决8皇后n皇后问题
数据结构课程设计
学院: 信息科学技术学院
专业: 电子信息工程(1)
姓名: 谢后乐
学号: 215
N皇后问题
N皇后问题:
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后，任何2个皇后不妨在同一行或同一列或同一斜线上。
回溯法简介:
回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
我们发现，对于许多问题，所给定的约束集D具有完备性，即i元祖(x1，x2，…，xi)满足D中仅涉及到x1，x2，…，xi的所有约束意味着j(j<=i)元
，的所有约束，i=1，2，…，组(x1，x2，…)一定也满足D中仅涉及到x1，x2，…
n。换句话说，只要存在0?j?n-1，使得(x1，x2，…，)违反D中仅涉及到x1，x2，…，的约束之一，则以(x1，x2，…，)为前缀的任何n元组(x1，x2，…， j+1，…，)一定也违反D中仅涉及到x1，x2，…，xi的一个约束，n?i?j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组(x1，x2，…)违反D中仅涉及x1，x2，…，的一个约束，就可以肯定，以(x1，x2，…)为前缀的任何n元组(x1，x2，…，)都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。
空间树
回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造: 设Si中的元素可排成xi(1) ，xi(2) ，…，xi(mi-1) ，|Si| =mi，i=1，2，…，n。从根开始，让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边，按从左到右的次序，分别带权xi+1(1) ，xi+1(2) ，…，xi+1(mi) ，i=0，1，2，…，n-1。照这种构造方式，E中的一个n元组(x1，x2，…)对应于T中的一个叶子节点，T的根到这个叶子结点的路径上依次的n条边的权分别为x1，x2，…，，反之亦然。另外，对于任意的0?i?n-1，E中n元组(x1，x2，…)的一个前缀I元组(x1，x2，…，xi)对应于T中的一个非叶子节点，T的根到这个非叶子结点的路径上依次的I条边的权分别为x1，x2，…，xi，反之亦然。特别，E中的任意一个n元组的空前缀()，对应于T的根。 因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子节点，要求从T的根到该叶子结点的路径上依次的n条边相应带的n
个权x1，x2，…满足约束集D的全部约束。在T中搜索所要求的叶子节点，很自然的一种方式是从根出发，按深度优先的逐步深入，即依次搜索满足约束条件的前缀1元组(x1i)、前缀2元组(x1，x2)、…，前缀I元组(x1，x2，…，xi)，…，直到i=n为止。 在回溯法中，上述引入的树