资源描述：
《回溯法解决8皇后问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、算法设计与分析实验报告实验名称：用回溯法解决八阜P问题姓名：学号：江苏科技大学一、实验名称：回溯法求解8皇后问题二、学习知识：回溯算法的菽木思想是：从一条路往前走，能进则进，不能进则退回米，换一条路冉试。M溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含M题的所有解的解空间树屮，按照深度优先的策略，从根结点出发搜索解的空间树。算法搜索至解的空间树的任一结点吋，总是先判断该结点是否r定不包含问题的解。如果肯定不乜含，则跳过对以该结点为根的子树的系统搜索，逐层昀其祖先结点lul溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在川來求问题的所冇解时，耍
2、回溯到根，且根结点的所冇了•树都已被搜索遍方结朿。而M溯法在用来求M题的任一•解时，从要搜索到M题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适川于解•一些组合数较人的问题。三、问题描述(1)使川回溯法解决八皇后问题。8皇后问题：在8'8格的棋盘上放置彼此不受攻击的8个呈后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。8后问题等价于在8'8格的棋盘上放置8个皇P，任何2个皇P不放在同一行或同一列或同一斜线上。(2)用高级程序设计语言实现四、求解思路ProcedurePLACE(k)//如果一个皇后能
3、放在第k行和X(k)列，则返回true,否则返回false。X足一个全程数组，进入此过程吋已置入了k个值。ABS(r)过程返回r的绝对值//globalX(1:k);integeri,k;i^lwhilei〈kdoifX(i)=X(k)orABS(X(i)-X(k))=ABS(i-k)thenreturn(false)endifi<-i+lrepeatreturn(true)EndPLACEProcedureNQUEENS(n)//此过程使用回溯法求fll一个n*n棋盘上放置n个皇后，使其不能互相攻击的所有可能位置//integerk,n,X(1:n)X(l)<
4、-0;k<-lwhilek>0doX(k)<-X(k)+l//k是当前行;X(k)是当前列////对所冇的行，执行以下语句////移到下一列//whileX(k)<=nandNotPLACE(k)do//此处能放这个皇后吗//X(k)<-X(k)+1//不能放则转到下一列//repeatifX(k)<=nthen//找到一个位置//ifk=nthenprint(X)//是一个完整的解则打印这个数组//elsek^k+l;X(k)^0//否则转到下•一行//endifelsek<-k~l//回溯//endifrepeatEndNQUEENS五、算法实现木实验程序是
5、使川C#编写，算法实现如下：1.queen类一实现8皇后M题的计算，将结果存入数组。usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Collections;namespace_8Queen{publicclassQueen{publicstaticArrayListarr=newArrayList()://存放査询结果privatestaticbool口columflag=newbool[8]{true，true,true,true
6、,true,true,true,true};"夕iJiii•用标记true为可用privatestaticbool口leftflag=newbool[15]{true，true,true,true,true,true,true,true,true,true,true,true,true,true,true};//左行对魚线占用标记privatestaticbool[]rightflag=newbool[15]{true,true,true,true,true,true,true,true,true,true,true,true,true,true,true};/
7、/芯行对角线山川标Cprivatestaticint[,]position=newint[,]{{0,0,0,0,0,0,0,0),{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}，{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}};//皇后位置坐标publicstaticintsum=0;publicstaticvoidTryStep(inti)//i取值1至8for(intj=1;j<=8;j++)if(columflag[
8、j-1]&&leftfl
