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

数据结构课程设计






学院: 信息科学技术学院
专业: 电子信息工程(1)
姓名: 谢后乐
学号: 20101601310015

N皇后问题
N皇后问题:
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于再n×n的棋盘上放置n个皇后,任何2个皇后不妨在同一行或同一列或同一斜线上。
回溯法简介:
回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
我们发现,对于许多问题,所给定的约束集D具有完备性,即i元祖(x1,x2,…,xi)满足D中仅涉及到x1,x2,…,xi的所有约束意味着j(j<=i)元组(x1,x2,…)一定也满足D中仅涉及到x1,x2,…,的所有约束,i=1,2,…,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为止。在回溯法中,上述引入的树被称为问题P的