文档详情

回溯法解决8皇后问题实验报告.doc

发布:2016-12-13约7千字共8页下载文档
文本预览下载声明
算法设计与分析 实验报告 实验名称: 用回溯法解决八皇后问题 姓 名: 学 号: 江 苏 科 技 大 学 一、实验名称:回溯法求解皇后问题回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。 回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中,按照深度优先的策略,从根结点出发搜索解的空间树。算法搜索至解的空间树的任一结点时,总是先判断该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时,要回溯到根,且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时,只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题。 1)使用回溯法解决八皇后问题。 8皇后问题:在8*8格的棋盘上放置彼此不受攻击的8个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。8后问题等价于在8*8格的棋盘上放置8个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。 (2)用高级程序设计语言实现 四、求解思路 Procedure PLACE(k) //如果一个皇后能放在第k行和X(k)列,则返回true,否则返回false。X是一个全程数组,进入此过程时已置入了k个值。ABS(r)过程返回r的绝对值// global X(1:k); integer i,k; i(1 while ik do if X(i)=X(k) or ABS(X(i)-X(k))=ABS(i-k) then return (false) end if i(i+1 repeat return (true) End PLACE Procedure NQUEENS(n) //此过程使用回溯法求出一个n*n棋盘上放置n个皇后,使其不能互相攻击的所有可能位置// integer k,n,X(1:n) X(1)(0 ; k(1 // k是当前行;X(k)是当前列 // while k0 do // 对所有的行,执行以下语句 // X(k)(X(k)+1 //移到下一列// while X(k)=n and Not PLACE(k) do //此处能放这个皇后吗// X(k)(X(k)+1 //不能放则转到下一列// repeat if X(k)=n then //找到一个位置// if k=n then print (X) //是一个完整的解则打印这个数组// else k(k+1;X(k)(0 //否则转到下一行// end if else k(k-1 //回溯// end if repeat End NQUEENS 五、算法实现 本实验程序是使用C#编写,算法实现如下: 1.queen类—实现8皇后问题的计算,将结果存入数组。 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; namespace _8Queen { public class Queen { public static ArrayList arr = new ArrayList(); //存放查询结果 private static bool[] columflag = new bool[8]{true, true,true,true,true,true,true,true};//列占用标记 true为可用 private static bool[] leftflag = new bool[15]{true,true,true, true,true,true,true,true,true,true,true,true,true,true,true};//左行对角线占用标记 private static bool[] rightfla
显示全部
相似文档