深圳大学实验报告 课程名称：算法分析与复杂性理论 实验项目名称：八皇后问题 学院：计算机与软件学院 专业：软件工程 指导教师：杨烜 报告人：学号：班级：15级软工学术型实验时间：2015-12-08 实验报告提交时间：2015-12-09 教务部制
一．实验目的 1.掌握选回溯法设计思想。 2.掌握八皇后问题的回溯法解法。 二．实验步骤与结果 实验总体思路： 根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。测试数据模块主要调用判断模块进行判断，完成测试。用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。相应结果和过程如下所示（代码和结果如下图所示）。 回溯法的实现及实验结果： 1、判断函数 代码1： procedure BTrack_Queen(n) //如果一个皇后能放在第K行和X(k)列，则返回true，否则返回false。 global X(1:k);integer i,k i←1 while i
流程图 八皇后问题算法分析 在这个问题中首先定义的是一个用于构造界面的二位数组a【i】【j】和一个用于判断的表头数组number【】。在开始进行八皇后棋子排列的时候，首先对行进行递增循环，即i初始值为0，每次i++，i最大值为8的循环。在每次循环中产生一个小于8的随机数q，然后判断表头数组number【】中number【q】位置的值是否为1，如果不是，则在二维数组a【i】【q】位置上打印表示棋子的“K”；如果为1，则返回产生随机数的步骤继续产生随机数。在循环到i>8时，跳出循环，这时候一个完整的八皇后排列也就出来了。 源代码： package queen; import java.awt.*; import java.awt.event.*; class equeen extends Frame implements ActionListener{ //构造界面和定义数组 Button enter; Button clean; Button exit; int number[] = new int[8]; int i,j,q; Label a[][] = new Label[8][8]; equeen(String s){ GridLayout grid; grid = new GridLayout(9,8); setLayout(grid); enter = new Button("begin"); clean = new Button("clean");
exit = new Button("esit"); for(int i = 0;i<8;i++){ for(int j = 0;j<8;j++){ a[i][j] = new Label(); if((i+j)%2==0)a[i][j].setBackground(Color.yellow); else a[i][j].setBackground(Color.gray); add(a[i][j]); } } for(int i = 0;i<8;i++){ number[i] = 0;//初始化判断数组 } add(enter); add(clean); add(exit); enter.addActionListener(this); clean.addActionListener(this); exit.addActionListener(this); setBounds(100,100,300,300); setVisible(true); validate(); } public void actionPerformed(ActionEvent e){ if(e.getSource()==enter){ for(int i =0;i<8;i++){ for(int j=0;j<8;j++){ a[i][j].setText(""); } } for(int i =0;i<8;i++){ while(true){ q = (int)(Math.random()*8); if(number[q]==0){ a[i][q].setText("K"); number[q] = 1; break; } else if(number[q]!=0) continue; } } for(int i = 0;i<8;i++){ number[i] = 0; } }
工学院 数据结构课程设计报告设计题目：八皇后 2008 年 6 月25 日 设计任务书
摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法
目录 1. 课题综述 (1) 1.1课题的来源及意义 (1) 1.2面对的问题 (1) 2. 需求分析 (1) 2.1涉及到的知识 (2) 2.2软硬件的需求 (2) 2.3功能需求 (2) 3. 概要设计 (2) 4. 详细设计和实现 (3) 4.1算法描述及详细流程图 (3) 4.1.1算法描述 (3) 4.1.2算法流程图 (3) 5. 代码编写及详细注释 (4) 6. 程序调试 (8) 6.1调试过程、步骤及遇到的问题 (8) 7. 运行与测试 (8) 7.1运行演示 (8) 总结 (10) 致 (11)
参考文献 (12) .
1. 课题综述 1. 1课题的来源及意义 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。 到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。 1. 2 面对的问题 1）解决冲突问题： 这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； 2）使用数据结构的知识，用递归法解决问题。 2. 需求分析
M文件 function PlaceQueen(row,matrix,N)%回溯法放置皇后 if row>N PrintQueen(N,matrix);%打印棋盘 else for col=1:N matrix(row,col)=1; if row==1||Conflict(row,col,N,matrix)%检测是否冲突 PlaceQueen(row+1,matrix,N); end matrix(row,col)=0; end end %子函数：检测冲突 function result=Conflict(row,col,N,matrix)%检测是否冲突 result=1; for i=1:row-1 for j=1:N if matrix(i,j)==1 if ((j==col)||(abs(row-i)==abs(col-j)))%是否产生冲突：在同一直线，斜线上 result=0; break; end end end if result==0 break; end end %子函数：打印棋盘信息
function PrintQueen(N,matrix) global solutionNum; %定义全局变量，来累积方法数 solutionNum=solutionNum+1; disp(['第',num2str(solutionNum),'种方法：']) disp(matrix) 脚本文件 clear all clc global solutionNum; solutionNum=0;%全局变量记录方法数 N=8;%皇后个数 matrix=zeros(N);%存储皇后位置信息 PlaceQueen(1,matrix,N)%调用放置方法
计算机科学与技术专业 数据结构课程设计报告设计题目：八皇后问题
目录 1需求分析 (3) 1.1功能分析 (3) 1.2设计平台 (4) 2概要设计 (4) 2.1算法描述 (5) 2.2算法思想 (6) 2.3数据类型的定义 (6) 3详细设计和实现 (7) 3.1算法流程图 (7) 3.2 主程序 (7) 3.3 回溯算法程序 (8) 4调试与操作说明 (10) 4.1调试情况 (10) 4.2操作说明 (10) 5设计总结 (12) 参考文献 (13) 附录 (13)
1需求分析 1.1功能分析 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有92个解答。 1、本演示程序中，利用选择进行。程序运行后，首先要求用户选择模式，然后进入模式。皇后个数设0 八皇后问题学 2012年 9 月 5 日 目录 一、选题 1.1背景知识 (2) 1.2设计目的与要求 (2) 二、算法设计 2.1问题分析 (3) 2.2算法设计 (3) 三、详细设计 3.1源程序清单 (4) 四、调试结果及分析 4.1调试结果 (6) 4.2调试分析 (7) 五、课程设计总结 5.1总结及体会 (7) 六、答辩 6.1答辩记录 (8) 6.2教师意见 (8) 一、选题及背景知识 1.1 背景知识 在国际象棋中，皇后是一个威力很大的棋子，她可以“横冲直撞”（在正负或垂直方向走任意步数），也可以“斜刺冲杀”（在正负45度方向走任意步数），所以在8*8的棋盘上要布互相不受攻击的皇后，最多只能布八个，共92种布法，再也不能有别的布法了——这就是著名的八皇后问题 在8*8的国际象棋棋盘上，放置八个皇后，使得这八个棋子不能互相被对方吃掉。也就是说一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 1.2 设计要求 要求：·判断在国际象棋中，能否在空棋盘上摆放8个皇后，并使其中任意两个皇后不能在同一行，同一列或同一对角线上。 ·编写完整的摆放八皇后问题的程序 ·具体要求第一个皇后的起始位置由键盘输入 二、算法设计 2.1问题分析 设计——图形表示下图中，Q代表皇后 假设在第k列上找到合适的位置放置一个皇后，要求它与第1——k-1列上的皇后不同行、列、对角线；可以从图上找到规律：不同列时成立，皇后放在第k列上；讨论行时，第j个皇后的位置（a[j] ，j）要与（i，k）位置的皇后不同行；如果同在／斜线上，行列值之和相同；如果同在＼斜线上，行列值之差相同；如果斜线不分方向则同一斜线上两皇后的行号之差的绝对值与列号之差的绝对值相同,可表示为（|a[j]-i|=|j-k|）。 2.2 算法设计 利用计算机运行速度快的特点，采用枚举法，逐一尝试各种摆放方式，来判断最终摆法。其中判断是否同在对角线上用到了：行数差的绝对值与列数差的绝对值相等， 淮阴工学院 数据结构课程设计报告 设计题目：八皇后 系（院）:计算机工程系 专业：信息安全 班级：信息 1 0 6 学生姓名: 叶青学号:1061303127 指导教师:张亚红寇海洲胡荣林夏森 学年学期: 2007 ~ 2008 学年第 2 学期 2008 年 6 月25 日 设计任务书 摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法 目录 1. 课题综述 (1) 1.1课题的来源及意义 (1) 1.2面对的问题 (1) 2. 需求分析 (1) 2.1涉及到的知识 (1) 2.2软硬件的需求 (1) 2.3功能需求 (2) 3. 概要设计 (2) 4. 详细设计和实现 (2) 4.1算法描述及详细流程图 (2) 4.1.1算法描述 (3) 4.1.2算法流程图 (3) 5. 代码编写及详细注释 (4) 6. 程序调试 (7) 6.1调试过程、步骤及遇到的问题 (7) 7. 运行与测试 (7) 7.1运行演示 (7) 总结 (9) 致谢 (10) 参考文献 (11) . 课程设计报告 课程名称数据结构课程设计 课题名称八皇后问题演示 专业通信工程 班级通信工程1081 学号201013120103 姓名刘献文 指导教师田娟秀郭芳 2012年7 月 6 日 湖南工程学院 课程设计任务书 课程名称数据结构 课题八皇后问题演示 专业班级通信工程1081 学生姓名刘献文 学号201013120103 指导老师田娟秀郭芳 审批 任务书下达日期2012 年7 月 1 日 任务完成日期2012 年7 月 6 日 1设计内容与设计要求 1.1设计内容 （4）课题四：八皇后问题演示 八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。 设计思路：解决8皇后时，在安放第i行皇后时，需要在列的方向从1到n试 探(j =1,…, n)：首先在第j列安放一个皇后，如果在列、主对角线、次对角线方 向有其它皇后，则出现攻击，撤消在第j列安放的皇后。如果没有出现攻击，在第 j列安放的皇后不动，递归安放第i+1行皇后。 对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动。要求用Turbo C或VC6.0 MFC实现的八皇后问题的图形程序，能够演示全部的92组解。 1.2 选题方案： 所选题目根据学号确定，学号模6加1，即（学号%6+1）。如你的学号为9，则 所选题目号为：9%6+1＝（题目4）。注意，所有的课题都要求用图形方式演示步骤 和结果。同学们可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法。 1.3设计要求： 1.3.1 课程设计报告规范 （1）需求分析 a.程序的功能。 b.输入输出的要求。 （2）概要设计 a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块 的功能。 算法设计与分析 实验报告 —八皇后问题 - 姓名：崔明鑫 学号：08208012 班级：软件83 【问题描述】 在国际象棋盘上放八个皇后，要求任一皇后吃不到别人，也不受其他皇后的攻击，求出问题的所有解。 【问题分析&算法设计】 用8元组x[1: n]表示8后问题。其中x[ i]表示皇后i放在棋盘的第i行的第x[ i]列。由于不允许将2个皇后放在一列，所以解向量中的x[ i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。故若2个皇后放置的位置分别是（i，j）和（k，l），且i – j = k – l或i + j = k + l，则说明这2个皇后处于同一斜线上。这两个方程分别等价于i – k = j – l和i – k = l – j。由此可知，只要|i - k| = |j - l|成立，就表明2个皇后位于同一条斜线上。问题的隐约束化成了显约束。用回溯法解决8皇后问题时，用完全8叉树表示解空间。 【算法实现】 #include "stdio.h" #include "math.h" #include "iostream.h" #define N 8 /* 定义棋盘大小*/ static int sum; /* 当前已找到解的个数*/ static int x[N]; /* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列*/ /* 每找到一个解,打印当前棋盘状态*/ void Show() { sum++; cout << "第" << sum << "种情况：" << endl; cout << "坐标为:\t"; for(int k = 0; k < N; k++) 算法设计及分析 n皇后问题---回溯求解 国际象棋中皇后威力很大，它可以象“车”一样沿直线上下或左右移动；也可以如同 “象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么， 在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢？这个问题是伟 大数学家高斯在十九世纪中期提出来的，并作了部分解答。高斯在棋盘上放下了N个互不攻 击的皇后，他还认为可能有N种不同的放法，这就是有名的“N皇后”问题。如果你动手试试， 就一定会发现开头几颗皇后很容易放置，越到后来就越困难。由于我们的记忆有限，很可能 在某个位置放过子后来证明不行取消了，但是以后又重新放上子去试探，这样就会不断地走 弯路，花费大量的精力。因此，必须找到一个简易有效、有条不紊的法则才行。 回溯法的基本思想： 对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的 每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况； 从而得出结果。在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这 也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些不可能的解，这样就不 必继续把解的剩余部分列出从而节省部分时间。 不妨以8皇后为例，设8皇后为x i，她们分别在第i行（i=1,2,3,4,5,6,7,8）,这样问 题的解空间就是一个8个皇后所在列的序号，为n元一维向量（x1,x2,,x3,x4,x5,x6,x7,x8），搜 索空间是1≤x i≤8（i=1,2,3,4,5,6,7,8）,共88个状态。约束条件是8个点 （1,x1）,(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)不在同一列和同一对角线上。虽 然问题共有88个状态，但算法不会真正地搜索这么多的状态，因为回溯法采用的是“走不通 就掉头”的策略，而形如（1,1,x3,x4,x5,x6,x7,x8）的状态共有86个，由于1,2号皇后在同一 列不满足约束条件，回溯后这些状态是不会搜索的。 算法设计： 我们用三个数组c,b,d分别记录棋盘上的n个列，2n-1个住对角线和2n-1个副对角线的 占用情况。用i,j分别表示皇后所在的行列，用表达式i-j+n对主对角线编号，范围是1～2n-1， 用i+j为负对角线编号，范围为2～2n. 程序代码： #include"stdio.h" int a[20],b[20],c[40],d[40],n,i,k; int t=0; //t记录解的个数 void output() { t=t+1; printf("第%d个解:",t); for(k=1;k<=n;k++) printf("%d",a[k]); printf("\n"); } void find(int i) { int j; for(j=1;j<=n;j++) //第i个皇后有n种可能位置 if(b[j]==0&&c[i+j]==0&&d[i-j+n]==0) //判断位置是否冲突 {a[i]=j; //摆放皇后 b[j]=1; //占领第j列 c[i+j]=1;//占领两个对角线 d[i-j+n]=1; if(i 数据结构课程设计报告 任务 要求 八皇后问题JAVA程序 public class Queen { static int QueenMax = 8; static int times = 0; static int chess[] = new int[QueenMax]; public static void placequeen(int num) { int i=0; boolean save[] = new boolean[QueenMax]; for(;i 淮阴工学院 数据结构课程设计报告设计题目：八皇后 2008 年 6 月25 日 设计任务书 课题 名称 八皇后 设计目的1.用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既 攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现． 2.通过这次课程设计,提高自己的编程能力,熟悉c++的编程坏境,为以后的程 序开发打下基础. 实验环境1）系统要求：win98以上操作系统；2）语言平台：tc++或vc++6.0；3）执行文件：八皇后.exe 任务要求试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。 工作进度计划 序号起止日期工作内容 1 2008.6.23~2008.6.24查阅相关内容 2 2008.6.24~2008.6.25编写代码及实习报告 3 2008.6.25~2008.6.26完善课程设计报告 4 2008.6.26~2008.6.27答辩 指导教师（签章）： 2008 年 6 月30 日 摘要： 八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。 而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．使用递归方法最终将其问题变得一目了然，更加易懂。 关键词：八皇后; c++; 递归法 递归算法——八皇后问题 1、背景问题描述 八皇后问题是一个古老而著名的问题，该问题的目标是在8×8的国际象棋棋盘上放置八个皇后，使得任意两个皇后都不在同一行，或同一列或同一对角线上。如图1所示就是八皇后问题的一个解。 图1 八皇后问题的一个解 1854年在柏林的象棋杂志上不同的作者发表了40种不同的解。大数学家高斯认为有76种不同的方案。后来有人用图论的方法算出92种不同的解。 能否利用程序算出所有满足条件的解的数目呢？ 2、抽象表示及存储 对于这种矩形排列的棋盘而言，用二维数组存储棋盘的状况是最容易想到的方法。可以设置一个8*8的二维数组，令有棋子的位置为1，无棋子的部分为0。 事实上，由于8个皇后中任意两个皇后都不在同一行，因此8个皇后只能各自占据一行。不妨认为8个皇后编号为0、1、……、7，它们各自占据棋盘的第1行、第2行、……、第8行。从而可以使用长度为8一维数组表示棋盘状态，数组元素的下标表示棋子所在行，数组元素的值表示各个棋子所在的列。 使用的存储方式不同，其采用的算法已有很大区别。 3、问题分析及算法设计 假定用二维数组A存储棋盘的情况，可以考虑下面两种思路。 思路一：不考虑任何限制的穷举法。 用8×8的二维数组存储棋盘，若在(i,j)处有子，则令A[i][j]=1，否则A[i][j]=0。于是8个棋子第1个有64种摆放方法，第2个有63种放法，……，第8个有57种放法，则所有摆放方法有64×63×62×…×57种。可以列举每一种摆法，而后考察每种方法是否符合条件。这个计算量非常大。 思路二：考虑经过优化的穷举法(二维数组方案)。 若8个棋子位于8行8列的棋盘中，要求任意两个不同行、不同列，则任一解必然是各行、各列只包含一个棋子，其它情况必然不是解。于是可以做个8重循环，把每个皇后安排在每行的每个位置都试一遍。算法如下： 将整个棋盘数组赋值为0； for(1号皇后从1行1列到1行8列) { 将1号皇后能控制的线路(横向、竖线、斜线)全部设为1； for(2号皇后从2行1列到2行8列) { if(2号皇后控制的线路全部为0) { 将2号皇后能控制的线路(横向、竖线、斜线)全部设为2； for(3号皇后从3行1列到3行8列) { if(3号皇后控制的线路全部为0) { 将3号皇后能控制的线路全部设为3； …… for(8号皇后从8行1列到8行8列) { if(8号皇后控制的线路全部为0) { 将8号皇后能控制的线路全部设为8； 记录该棋盘为一个解； } 将8号皇后控制的线路全部恢复为0； } …… } 将3号皇后控制的线路全部恢复为0； } } 将2号皇后控制的线路全部恢复为0； } 将1号皇后控制的线路全部恢复为0 } 上述算法中的多重循环虽易于理解，但程序嵌套结构较为复杂，形式死板，不易扩展。事实上，可以将某一个棋子在一行中的试探过程写成一个递归函数，这样程序的灵活性就大为提高了。 对于本问题实际上还可以用一维数组的存储形式解决，下面的思路正是如此。 思路三：考虑经过优化的穷举法(一维数组方案)。 在思路二的算法中，摆放第i行棋子时，判断可行性的方法是考察第i个棋子的控制区域是否和第1到第i-1个棋子的控制区域是否有交叉。现在将判断可行性方法改变如下： 软件工程上机报告 实验名称：八皇后问题图形界面求解 姓名：郭恂 学号：2011011435 班级：11级数学班 中国石油大学（北京）计算机科学与技术系 一、试验程序截图： 点击显示下一组解即可显示下一组解： 同样的，如果点击上一组解即可显示上一组解。 若在第1组解时点击显示上一组解会弹出报错提示框。 同样，若在第92组解点击显示下一组解也会弹出报错提示框： 二、程序代码 程序使用Java语言编写，编写环境为jdk1.6.0_18。使用编程开发环境eclipse.exe编写。 本程序创建了两个类，两个类在同一个工程中。其中Queen类的作用仅仅用来保存八皇后问题计算结果的数据，便于画图时使用。 本程序大概由两部分组成，第一部分是解八皇后问题，第二部分是画图。 程序源代码为： 类1： public class Queen { public int[] x=new int[8]; public int[] y=new int[8]; public String name; } 类2： import javax.swing.*; import java.awt.event.*; import java.awt.*; import javax.swing.JOptionPane; public class bahuanghou extends JFrame implements ActionListener { //JLabel[] l; int number=0; //当前显示的解的编号 int sum=0; //所有解得数量 JLabel l2; JButton b1,b2; //b1为显示下一组解得按钮，b2为显示上一组解得按钮。 Queen[] q=new Queen[128]; //得到的解储存在Queen类的数组里面。 private Image bomb1= Toolkit.getDefaultToolkit().getImage("D:\\qizi1.JPG"); //黑格棋子为bomb1 private Image bomb2= Toolkit.getDefaultToolkit().getImage("D:\\qizi2.JPG"); //白格棋子为bomb2 public bahuanghou() //构造方法，初始化窗口。 { Queen(); //调用Queen函数解八皇后问题。 数据结构课程设计报告 八皇后问题 班级：*** 姓名：*** 学号：*** 八皇后问题 1、问题分析 八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850提出；在8×8格的国际象棋上摆放八皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后人有人用图论的方法解出92宗结果。 八皇后问题是在8*8的国际象棋棋盘上，安放8个皇后，要求没有一个皇后能够“吃掉”任何其他一个皇后，即没有两个或两个以上的皇后占据棋盘上的同一行、同一列或同一条对角线。 八皇后在棋盘上分布的各种可能的格局，其数非常大，但是可以将一些明显不满足问题要求的格局排除掉。由于任何两个皇后不能同行，即每一行只能放置一个皇后，因此将第i个皇后放置在第i行。这样在放置第i个皇后时，只要考虑它与前i-1个皇后处于不同列和不同对角线位置上即可。 2、算法描述 从第一行起逐行放置皇后，每放置一个皇后均需要依次对第1，2…8列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不与已经放置的其他皇后冲突，则将该行的列位置保存在栈中，然后继续在下一行上寻找安全位置；若当前试探的列位置不安全，则用下一列去试探，当8列位置试探完毕都未找到安全位置时，就退栈回溯到上一行，修改栈顶保存的皇后位置，然后继续试探。 该算法抽象的描述如下： （1）置当前行当前列均为1； （2）While（当前行号＜＝8）； （3）{检查当前行，从当前列起逐列试探，寻找安全列号； （4）if（找到安全列号） （5）放置皇后，将列号放入栈中，并将下一行置为当前行，第1列置为当前列； （6）else （7）退栈回溯到上一行，移去该行已经放置的皇后，已该皇后所在列的下一列作为当前列； （8）} 2．1算法求精 要对上述抽象算法进行逐步求精，就需要确定相应的存储结构和有关的数据类型。当前行和列分别用i和j表示；用数组s[1…8]表示顺序栈，栈空间的下标值表示皇后所在的行号，栈的内容是皇后所在的列号。例如，若皇后放在位置（i,j）上，则将j压入栈中，即s[i]=j。为了便于检查皇后之间是否冲突，我们增加三个布尔数组（初始值为真），将与检查有关的信息事先保存起来。定义如下： 算法设计与分析 实验报告 实验名称：用回溯法解决八皇后问题姓名： 学号： 江苏科技大学 一、实验名称：回溯法求解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 i 数据结构课程设计报告 设计题目：八皇后问题 系（院）:数学学院 专业：信息与计算科学 班级： 02班 学生姓名王天宇学号: 20096390 指导教师: 设计任务书 1. 课题综述 1. 1课题的来源及意义 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。 到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。 1. 2 面对的问题 1）解决冲突问题： 这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； 2）使用数据结构的知识，用递归法解决问题。 2概要设计 本课件学生是用循环递归循环来实现的，分别一一测试了每一种摆法，并把它拥有的92种变化表现出来。在这个程序中，我的主要思路以及思想是这样的：1）解决冲突问题： 这个问题包括了行，列，两条对角线； 列：规定每一列放一个皇后，不会造成列上的冲突； 行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态； 对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。 因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。 2）数据结构的实现 而对于数据结构的实现，学生则是着重于: 数组a[I]：a [I]表示第I个皇后放置的列；I的范围：1..8; 对角线数组：b[j](主对角线),c[j]（从对角线），根据程序的运行，去决定主从对角线是否放入皇后； 3. 详细设计和实现 4.1.1 算法描述 A、数据初始化。 B、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要 求），先测试当前位置（n，m）是否等于0（未被占领）。如果是，摆放第n个皇后，并宣布占领（记得姚横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当n<=8，m=8时，发现此时已无法摆放时，便要进行回溯。从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，这种不断“回溯”的寻找解的方法，称为“回溯法”。 C、使用数组实现回溯法的思想。 D、当n>8时，便打印出结果。 E、输出函数我使用printf输出，运行形式为：第m种方法为：* * * * * * * * 5. 代码编写及详细注释 XX级数据结构实验报告 实验名称：实验二——栈和队列 学生姓名：韩博 班级：2009211121 班内序号：01 学号：09210604 日期：10.11.25 1．实验要求 【实验目的】 1、进一步掌握指针、模板类、异常处理的使用 2、掌握栈的操作的实现方法 3、掌握队列的操作的实现方法 4、学习使用栈解决实际问题的能力 5、学习使用队列解决实际问题的能力 【实验内容】 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 提示： 1、可以使用递归或非递归两种方法实现 2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析 2.1存储结构 存储结构：栈（递归） 2.2 关键算法分析 【设计思想】 由于八皇后问题，可以分解成算法相同的子问题，所以使用递归的方法 【伪代码】 1、输入皇后个数n 2、k=1 3、判断k是否大于n 3.1是：打印一组可能 3.2否：循环行位置1~n 判断该位置是否符合要求，若符合记录q[k]的坐标y值 k+1重复3 【关键算法】 1、递归 void Queen::queen(int n) //递归函数的具体定义 { if(n==Number+1) //如果一到八行都已安排了皇后，则输出皇后 位置 {Print();return;} for(int i=1;i<=Number;i++) //从行号n=1开始逐个试探，即从i=1列开始 {Site[n]=i; if(IsValid(n)) //如果第n行可以取第i列上的位置，则开始试探第n+1行 {queen(n+1);} int Queen::IsValid(int n) //判定位置函数的具体定义，当皇后位于第n行时 {for(int m=1;m八皇后问题 C语言程序设计
八皇后问题的解决完整文档
数据结构课程设计之_八皇后问题
算法设计与分析实验报告—八皇后问题
n皇后问题算法设计
八皇后问题数据结构课程设计报告
八皇后问题
设计任务书
课题 八皇后 名称 1. 2. 3. 4. 调研并熟悉八皇后的基本功能、数据流程与工作规程； 学习八皇后相关的算法和基于 VC++集成环境的编程技术； 通过实际编程加深对基础知识的理解，提高实践能力； 学习开发资料的收集与整理，学会撰写课程设计报告。
设计 目的
实验 环境
1. 微型电子计算机（PC）； 2. 安装 Windows 2000 以上操作系统，Visual C++6.0 开发工具。
1. 利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及设 计要求，注意材料收集与整理； 2. 在第 16 周末之前完成预设计，并请指导教师审查，通过后方可进行下一 步工作； 3. 本课题要求至少用三种方法解决八皇后问题，输入棋盘的阶层，然后显示 共有多少种布局方案，并显示每一种方案的具体情况。 4. 结束后，及时提交设计报告（含纸质稿、电子稿），要求格式规范、内容 完整、结论正确，正文字数不少于 3000 字（不含代码）。 工作进度计划 起止日期 工 作 内 容
序号
1
2009.06.7~2009.06.7
在预设计的基础上， 进一步查阅资料， 完善设计方案， 形成书面材料。 设计总体方案，构建、绘制流程框图，编写代码，上 机调试。
2
2009.06. 7~2009.06.10 2009.06.11~2009.06.1 2 2009.06.12~2009.06.1 3
3
测试程序，优化代码，增强功能，撰写设计报告。
4
提交软件代码、设计报告，参加答辩，根据教师反馈 意见，修改、完善设计报告。
指导教师（签章）：
年
月
日
摘要： 众所周知的八皇后问题是一个非常古老的问题，具体如下：在 8*8 的国际象棋棋 盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处 于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础。要求编写实现八 皇后问题的递归解法或非递归解法，对于任意给定的一个初始位置，输出八皇后问题 的一个布局。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及 变通能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题 和解决问题的作风和能力。八皇后问题JAVA程序
八皇后问题的解决完整文档
8皇后问题分析与解法
八皇后问题实验报告
八皇后问题
回溯法解决8皇后问题实验报告
八皇后问题课程设计报告
c++利用栈解决八皇后问题_数据结构实验报告
相关主题
文本预览