软件工程上机报告
实验名称：八皇后问题图形界面求解
姓名：郭恂
学号：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函数解八皇后问题。
this.setBounds(400, 200, 500, 500); //设置窗体大小为(500,500),起始位置为(400,200)
this.setVisible(true); //设置窗体可视为true
this.setDefaultCloseOperation(EXIT_ON_CLOSE); //设置窗体右上角的功能
this.setLayout(new BorderLayout()); //窗体采用边布局
//北部
l2=new JLabel("八皇后问题共有"+(sum)+"组解,当前为第"+(number+1)+"组解");
this.add(l2,"North");
//中部
//中部用paint函数来画八皇后问题的解。
//南部
JPanel p2=new JPanel(); //南部使用一个流布局的panel。
p2.setLayout(new FlowLayout());
this.add(p2,"South");
b2=new JButton("显示上一组解");
b2.addActionListener(this); //按钮注册事件监听器
p2.add(b2);
b1=new JButton("显示下一组解");
b1.addActionListener(this); //按钮注册事件监听器
p2.add(b1);
}
//解八皇后问题的函数
public void Queen()
{
int num=0; //记录解得数量。与类成员sum作用相同，只不过sum保存在类中，num用于给Queen的数组赋值。
int n=8; //皇后上限为8
int[] x=new int[9]; //原本应该是长度为8的数组，这里为了后续计算方便，采用长度为9的数组，其中x[0]=0时不占任何内容的。x[1]为第一行的皇后棋子。
x[0]=x[1]=0; //x[i]代表第i行的皇后，x[i]的值代表该皇后所在的列数。
int k=1;
while(k > 0)
{
x[k]+=1; //转到下一行
while (x[k]<=n && this.Place(k,x)==false)
{
//如果无解，最后一个皇后就会安排到格子外面去
x[k]+=1;
}
if(x[k]<=n)
{
//第k个皇后仍被放置在格子内，有解
if(k==n)
{
this.q[num]=new Queen(); //开拓保存解得空间
for(int i=0;i { q[num].x[i]=i; //第i个皇后所在的行数为i q[num].y[i]=x[i+1]-1; //第i个皇后所在的列数为 x[i+1]-1 } num++; sum++; } else { k++; x[k]=0; //转到下一行 } } else //第k个皇后已经被放置到格子外了，没解，回溯 k--; //回溯 } } boolean Place(int k,int[] x) //判断第k个皇后能否放在第x[k]列上。 { int i = 1; while( i < k) { if( x[i]==x[k] || (Math.abs(x[i]-x[k]) == Math.abs(i-k)) ) //x[i]==x[k]用来判断第K个是否与之前的皇后在同一列。(Math.abs(x[i]-x[k]) == Math.abs(i-k))用来判断第k个皇后是否与之前的皇后在同一条斜线上。 return false; i++; } return true; } public void paint(Graphics g) { super.paint(g); //底色为灰 g.setColor(Color.GRAY); g.fillRect(50,50,400,400); //画棋盘 int i,j; for(i=0;i<8;i++) //黑白格相间，最左上角(0,0)为白格。 for(j=0;j<8;j++) { if((i+j)%2==0)g.setColor(Color.WHITE); //i+j为偶数时 是白格，i+j为奇数时是黑格。 else g.setColor(Color.BLACK); g.fillRect(70+45*i,70+45*j,45,45); } //画棋子 for(i=0;i<8;i++) { if((this.q[number].x[i]+this.q[number].y[i])%2==0) //棋子的x+y为偶数时用白格棋子bomb2 g.drawImage(bomb2, 70+this.q[number].y[i]*45,70+this.q[number].x[i]*45, 45, 45, this); else if((this.q[number].x[i]+this.q[number].y[i])%2==1) //棋子的x+y为奇数时用黑格棋子bomb1 g.drawImage(bomb1, 70+this.q[number].y[i]*45,70+this.q[number].x[i]*45, 45, 45, this); } } public void actionPerformed(ActionEvent e) //事件监听器 { if(e.getSource()==b1) //事件源为按钮1时“显示下一组解”。 { if(number<(sum-1)) { this.number++; //当前显示解序号+1 l2.setText("八皇后问题共有"+(sum)+"组解,当前为第 "+(number+1)+"组解"); //提示信息变更。 repaint(); //重画 } else JOptionPane.showMessageDialog(null,"这已经是最后一组解了！"); //越界时提示报错，然后什么也不做。 } else if(e.getSource()==b2) //事件源为按钮2时"显示上一组解 "，与按钮b2同理。 { if(number>0) { this.number--; l2.setText("八皇后问题共有"+(sum)+"组解,当前为第 "+(number+1)+"组解"); repaint(); } else JOptionPane.showMessageDialog(null,"这已经是第一组解了！"); } } public static void main(String args[]) { new bahuanghou(); //主函数中新建实例，开拓窗体。 } } 三、程序编写过程。 首先我把程序分为两部分： 第一部分的任务是构建窗体，画棋盘、棋子。 第二部分的任务是求解八皇后问题。 我首先考虑的时第一部分如何能获得第二部分求得的解。如是我编写了public class Queen ，并用它创建了一个数组，这样第二部分中求得解保存在数组中，第一部分绘图时可以随时取出来使用。 之后我先开始编写的第一部分，构建窗体， 设置窗体的大小为（500，,500） 设置布局，可见，将按钮和标签加入窗体中后，我开始考虑如何绘制棋盘、棋子，以及相应的解的显示方法。 我首先想以其中（400,400）的区域作为画布，长和宽分别留了100像素，也就是上下左右各50像素。涂为灰色。 然后我去网上查找国际象棋棋盘的图像，棋盘横竖为8个格子。如果画布上画满棋盘的话每个格子的长和宽都是（400/8）=50的，但我觉得整个棋盘占满画布应该不太好看（因为背景颜色太淡了，会与棋盘中白色的格子混淆），于是我就想让棋盘占据画布的中央部分，那么每个格子长和宽分别为45,45。这样就占了45*8=360的空间。长和款分别留了40像素，也就是上下左后各 20像素。 具体坐标如图所示。 然后考虑棋盘格子的绘制，棋盘黑白格相间，每行、每列格子数目均为8。每个格子长和宽分别为45,45。编写了一个循环很简单就绘制出来了。 之后是如何让棋子出现在棋盘上，这也是整个程序最困扰我的地方。我打算使用画笔Graphics 把棋子画上去，覆盖掉棋盘原本的格子。皇后的样子太过复杂，使用画笔画简单图形（椭圆、矩形）拼成一个皇后太难了，于是我上网找了相关的图片： 和。用windows自带的画图软件进行简单的处理后存为jpg格式。 画笔类自带有drawImage(Image img,int x,int y,int width,nt height,ImageObserver observer)函数可画jpg格式的图像。 将图片导入使用的Toolkit.getDefaultToolkit().getImage(URL)方法。其中URL为图片的绝对地址。 然后只需要计算好棋子的坐标画上去就好了。 这样的画绘图部分只剩下事件部分没有处理了。因为数组中没有存在解，不方便调试，所以我打算先解决第二部分再回来编写第一部分的事件处理。 我以第x[i]表示第i行的皇后，x[i]的值表示第i行的皇后在的列数。这样比创建一个8*8的数 组节省内存并且方便计算。我们都知道解决八皇后的问题要用递归的算法，如果第x[1]=1（第一个皇后放在第一行第一列的话），我们需要知道如何判断第2个皇后放在那里，第2行是肯定的，那么x[2]=?呢？如何递归呢？很容易想到的就是穷举法，把1-8的值都试一遍，选择合适的留下，不合适的舍去。 于是我编写了一个判断第k个皇后能否放在第x[k]列上的方法Place(int k,int[] x)，返回一个布尔型变量，返回true的话是可以，返回false是不可以。 这样问题似乎简单多了，剩下的就是如何递归。这里我才用了一个变量k，代表当前皇后的数量，即k=2时放第2个皇后，k=3时放第3个皇后。这样，如果第k个皇后成功放了，则k++。如果第k 个皇后没有成功放下（即放在格子外，x[k]的值大于8），则上一个皇后需要重放，则k--。这样的话穷举时x[k]只需要不断地累加就好了，当x[k]的值大于8时就是上一个皇后放错了，上一个皇后继续累加。 这样算法的时间复杂度为o(8^8)，将解存放在Queen数组之中。 之后设置变量number,为当前绘制的解得序号，编写事件监听器。给Unmber设置下线为0，上线为解得数目。整个程序编写完成。 具体调试中有很多小问题（诸如重写paint()方法后，JLabel无法调用setText方法等等问题），就不一一叙述了，重点的问题已经叙述完毕。 计算机科学与技术专业 数据结构课程设计报告设计题目：八皇后问题 目录 1需求分析 (2) 1.1功能分析 (2) 1.2设计平台 (3) 2概要设计 (3) 2.1算法描述 (4) 2.2算法思想 (5) 2.3数据类型的定义 (5) 3详细设计和实现 (6) 3.1算法流程图 (6) 3.2 主程序 (6) 3.3 回溯算法程序 (7) 4调试与操作说明 (9) 4.1调试情况 (9) 4.2操作说明 (9) 5设计总结 (11) 参考文献 (12) 附录 (12) 1需求分析 1.1功能分析 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。 在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有92个解答。 1、本演示程序中，利用选择进行。程序运行后，首先要求用户选择模式，然后进入模式。皇后个数设0 实验项目： 八皇后问题 1.实验目的： 通过求解皇后问题，熟悉深度优先搜索法DFS（回溯法（Backtracking Algorithms）技术。 2.实验内容： 由n2 个方块排成n行n列的正方形称为n元棋盘。如果两个皇后位于n元棋盘上的同一行、同一列或同一对角线上，则称它们在互相攻击。现要找出使棋盘上n个皇后互不攻击的布局。编制程序解决上述问题，以n=6运行程序，输出结果。 3.程序简介： 将n个皇后放到一个n*n的方阵中，要求每个皇后不在同一行同一列及同一对角线，我的程序是先把每个皇后放在了第零列，然后再按行检查，不符合要求继续下一列，若已经到这一行的最后一列，还没找到符合要求的位置，则回到上一行。 4.算法设计介绍： 定义一个一维数组，数组的下标是皇后所在位置的行数，数组存的值是皇后所在位置的列数，现将A[0]-A[n-1]都赋成零，然后随着检查的进行，皇后的位置也在不断地变化，最后找到一个符合要求的方阵时，本质上就是一个存放整数的一维数组，数组的下标是行数，存放的值是列数。 5.困难及解答 我很久以前就听说过八皇后问题，没想到现在轮到自己编了，一开始还真是特别糊涂呢，后来老师上课把算法大概讲了一遍，就清楚很多了，要说问题，就是一开始纠结怎么存放皇后，我开始想用二维数组着，后来老师说用一 维数组比较好做，我看了一下老师的算法，就明白了大概，经过一段时间就编出来了 5.心得 我编程变得还是很少，天天下决心说以后多编，也没践行，心想着吧，不挂在嘴上了，努力！ 6.程序清单 /* //我真诚地保证： //我独立完成了整个程序从分析、设计到编码的所有工作。 //如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中 //详细地列举我所遇到的问题，以及别人给我的提示。 //我的程序里中凡是引用到其他程序或文档之处， //例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段, //我都已经在程序的注释里很清楚地注明了引用的出处。 //我从未没抄袭过别人的程序，也没有盗用别人的程序，//不管是修改式的抄袭还是原封不动的抄袭。//我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转 文件名称： 创建者： 创建时间： 2011.4.14 安徽建筑工业学院数据结构设计报告书 院系数理系 专业信息与计算科学 班级11信息专升本 学号11207210138 姓名李晓光 题目八皇后 指导教师王鑫 1．程序功能介绍 答：这个程序是用于解决八皇后问题的。八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。我的程序进入时会让使用者选择程序的功能，选【1】将会通过使用者自己手动输入第一个皇后的坐标后获得答案；选【2】将会让程序自动运算出固定每一个皇后后所有的排列结果。 2．课程设计要求 答：（1）增加函数，完成每输入一组解，暂停屏幕，显示“按任意键继续！”。 （2）完善程序，编程计算八皇后问题共有集中排列方案。 （3）增加输入，显示在第一个皇后确定后，共有几组排列。 （4）将每组解的期盼横向排列输出在屏幕上，将五个棋盘并排排列，即一次8行同时输出5个棋盘，同样完成一组解后屏幕暂停，按任意键继续。 （5）求出在什么位置固定一个皇后后，解的数量最多，在什么位置固定皇后后，解的数量最少，最多的解是多少，最少的解是多少，并将最多，最少解的皇后位置及所有的解求出，同样5个一组显示。 3．对课程题目的分析与注释 答：众所周知的八皇后问题是一个非常古老的问题，问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击。按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子。因此，本课程设计的目的也是通过用C++语言平台在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现。使用递归方法最终将其问题变得一目了然，更加易懂。首先要用到类，将程序合理化：我编辑了一个盘棋8*8的类：class Board，还有个回溯法的类：class Stack，关键的类好了，然后编辑好类的成员，然后编辑主函数利用好这些类的成员，让其运算出结果。 4．程序设计和说明（说明算法思想、设计思路，给出重要的、关键的代码） 2007级数据结构实验报告 实验名称：实验二——栈和队列 学生姓名： 班级： 班内序号： 学号： 日期：2008年11月18日 1．实验要求 通过选择下面五个题目之一进行实现，掌握如下内容： ➢进一步掌握指针、模板类、异常处理的使用 ➢掌握栈的操作的实现方法 ➢掌握队列的操作的实现方法 ➢学习使用栈解决实际问题的能力 ➢学习使用队列解决实际问题的能力 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 提示： 1、可以使用递归或非递归两种方法实现 2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析 2.1 存储结构 采用栈存储，其结构图如下: 2.2 关键算法分析 函数原型： bool check(int i); 2.2.1.1.1自然语言： 检测至第i行所摆放的第i个皇后是否和之前的i-1个皇后发生冲突。如是，则返回0；反之，则当前布局合法，返回1。 判断两个皇后是否相互攻击的准则是：若两个皇后处于同一行，或处于同一列，或处于同一斜线，就能相互攻击。基于如上准则，函数check( )的工作原理是：考虑到数组的每个元素分别代表不同行的皇后，即每行只放置了一个皇后，所以不必考虑“同处一行相互攻击”的情形；对于同处一列，则语句： if(queen[s]==queen[t]) 就能判断出不同行的两个棋子是否同处一列；对于处于同一斜线的这种情况，首先，我们看出国际象棋的棋盘是一个八行八列的正方形。因此我们可将棋盘想象为数学上的笛卡尔平面坐标系，两颗棋子想象为平面上的两个点，就很容易发现，为保证两颗棋子不处于同一斜线，只要过这两个点的直线斜率不为1或-1，就能达到要求。由此可使用下列语句：if( abs(t-s) == abs(queen[s]-queen[t]) ) 其中t和s分别代表不同行的两个皇后，即数组queen[8]里不同下标的两个元素。 2.1.1.1.2伪代码： 第j行（j是第i行之前的i-1行中的一行）进行操作 如果第j行放置皇后的位置和第i行相同或者第j行放置皇后的位置与第i行的皇后在斜率为1或-1的直线上，则返回0 1.2否则，返回1 2.2.1.2放置新棋子 假设前i-1行的皇后棋子已被合法布置，现从第i行开始合法地摆放新棋子。如果当前的行数i已经大于等于8，则在总数上加1并输出当前的棋盘布局；否则将第i行的皇后放 八皇后问题有多少解 八皇后问题有92解。皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，‘ 即a=b1b2…b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。 //输入数据 //第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 <= b <= 92) //输出要求 //n行，每行输出对应一个输入。输出应是一个正整数，是对应于b 的皇后串 //输入样例 //2 //1 //92 //输出样例 //15863724 //84136275 解题思路一 因为要求出92种不同摆放方法中的任意一种，所以我们不妨把92种不同的摆放方法一次性求出来，存放在一个数组里。为求解这道题我们需要有一个矩阵仿真棋盘，每次试放一个棋子时只能放在尚未被控制的格子上，一旦放置了一个新棋子，就在它所能控制的所有位置上设置标记，如此下去把八个棋子放好。当完成一种摆放时，就要尝试下一种。若要按照字典序将可行的摆放方法记录下来，就要按照一定的顺序进行尝试。也就是将第一个棋子按照从小到大的顺序尝试；对于第一个棋子的每一个位置，将第二个棋子从可行的位置从小到大的顺序尝试；在第一第二个棋子固定的情况下，将第三个棋子从可行的位置从小到大的顺序尝试；依次类推。 首先，我们有一个8*8的矩阵仿真棋盘标识当前已经摆放好的棋子所控制的区域。用一个有92行每行8个元素的二维数组记录可行的摆放方法。用一个递归程序来实现尝试摆放的过程。基本思想是假设我们将第一个棋子摆好，并设置了它所控制的区域，则这个问题变成了一个7皇后问题，用与8皇后同样的方法可以获得问题的解。那我们就把重心放在如何摆放一个皇后棋子上，摆放的基本步骤是：从第1到第8个位置，顺序地尝试将棋子放置在每一个未被控制的位置上，设置该棋子所控制的格子，将问题变为更小规模的问题向下递归，需要注意的是每次尝试一个新的未被控制的位置前，要将上一次尝试的位置所控制的格子复原。 八数码问题 （一）问题描述 在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局和目标棋局，给出数码的移动序列。该问题称八数码难题或者重排九宫问题。 （二）问题分析 八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。 1、启发式搜索 由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。 由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度。 启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。 （三）数据结构与算法设计 该搜索为一个搜索树。为了简化问题，搜索树节点设计如下： struct Chess//棋盘 { int cell[N][N];//数码数组 int Value;//评估值 Direction BelockDirec;//所屏蔽方向 struct Chess * Parent;//父节点 }; int cell[N][N]; 数码数组：记录棋局数码摆放状态。 int Value; 评估值：记录与目标棋局差距的度量值。 Direction BelockDirec; 所屏蔽方向：一个屏蔽方向，防止回推。 Direction ：enum Direction{None,Up,Down,Left,Right};//方向枚举 struct Chess * Parent; 父节点：指向父亲节点。 下一步可以通过启发搜索算法构造搜索树。 1、局部搜索树样例： 《算法设计与分析》实验报告实验三回溯法 3.迷宫问题 一天Luna在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，. 和#，前者表示可以通行后者表示不能通行。同时当Luna处在某个格点时，她只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Luna想要从点A走到点B（不能走出迷宫）。如果起点或者终点有一个不能通行(为#)，则看成无法办到。 [输入] 第1行是测试数据的组数k，后面跟着k组输入。 每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n 的。 接下来是一个n * n的矩阵，矩阵中的元素为. 或者#。 再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb 行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。 1.八皇后问题 1.1解题思路 八皇后问题的解法，很简单的解法。通过回溯实现枚举。 对于当前行，尝试是否可在当前列放置皇后，然后进入下一行的尝试，同时尝试完毕以后，要将当前行回复（回溯），来进行下一次尝试。 到达最后一行的时候，即递归结束条件，打印结果即可。 1.2程序运行情况 1.3所有的皇后解 见附录。（毕竟92个解...） 1.4程序源码（含注释） 2. 24点问题 2.1 解题思路 这题虽然使用dfs很简单，但是有一点思维在里面。我很惭愧，自己没有想出来怎么如意的独立AC此题。 遇到的最大的问题——如何插入括号？枚举插入、和运算符一同排列都不靠谱。解决方法是：用同等的办法转化。每一次从待组合的是数字中，任取两个数，随机用运算符计算完毕后，再放回去。下一次计算，再次重复这个过程，可以等价为有括号的运算方式了。 遇到第二个问题——如何实现这种“任取两个数”的选择方式。这里就直接体现出了我个人能力的不足。居然没想到。尝试使用STL的set，但是没成功。这里借鉴了网上的AC 思路，我感到自己思维太僵硬。解决方法是——对于当前的运算状态中，用两个循环实现枚举两个数，计算为完毕以后，结果覆盖在数组序号小的那个数的位置，再将第二个数与最后一个数字交换即可进入下一个状态。回溯的时候，只需要回复小序号的数字的位置的值，以及再一次swap即可。（因为第二个数字只是swap却没有改变过内容）。 一个细节问题，就是加法和乘法是没有顺序的，减法和除法是有顺序的，以及除法要考虑0异常。一共是6次枚举即可。 2.2 测试样例 5 5 5 1 ans is YES 1 1 4 2 ans is :NO 2.3 程序运行情况 样例一： 软件工程上机报告 实验名称：八皇后问题图形界面求解 姓名：郭恂 学号：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.问题描述 设在初始状态下在国际象棋的棋盘上没有任何棋子（这里的棋子指皇后棋子）。然后顺序在第1行，第2行……第8行上布放棋子。在每一行中共有8个可选择的位置，但在任一时刻棋盘的合法布局都必须满足3个限制条件（1）任意两个棋子不得放在同一行（2）任意两个棋子不得放在同一列上（3）任意棋子不得放在同一正斜线和反斜线上。 2.基本要求 编写求解并输出此问题的一个合法布局的程序。 3、实现提示： 在第i行布放棋子时，从第1列到第8列逐列考察。当在第i行第j列布放棋子时，需要考察布放棋子后在行方向、列方向、正斜线和反斜线方向上的布局状态是否合法，若该棋子布放合法，再递归求解在第i+1行布放棋子；若该棋子布放不合法，移去这个棋子，恢复布放该棋子前的状态，然后再试探在第i行第j+1列布放棋子。 4 程序代码 #include static int c[15]; static int QueenNum=0;//记录总的棋盘状态数void qu(int i);//参数i代表行 int main() { int Line,Column; //棋盘初始化，空格为*，放置皇后的地方为@ for(Line=0;Line<8;Line++) { a[Line]=0; //列标记初始化，表示无列冲突 for(Column=0;Column<8;Column++) Queen[Line][Column]='*'; } //主、从对角线标记初始化，表示没有冲突 for(Line=0;Line<15;Line++) b[Line]=c[Line]=0; qu(0); return 0; } void qu(int i) 回溯法实验报告 回溯法实验报告 一、引言 回溯法是一种经典的算法解决方法，广泛应用于组合优化、图论、人工智能等领域。本实验旨在通过实际案例，深入探讨回溯法的原理、应用和优化方法。 二、实验背景 回溯法是一种通过不断尝试和回退的方式，寻找问题的解的方法。它适用于那些问题空间巨大且难以直接求解的情况。回溯法通过逐步构建解空间树，深度优先地搜索可能的解，并在搜索过程中剪枝，以提高搜索效率。 三、实验过程 我们选择了一个经典的回溯法问题——八皇后问题作为实验案例。该问题要求在一个8x8的棋盘上放置8个皇后，使得它们两两之间无法互相攻击。我们采用了递归的方式实现回溯法，并通过剪枝操作来减少搜索空间。 具体实验步骤如下： 1. 定义一个8x8的棋盘，并初始化为空。 2. 从第一行开始，逐行放置皇后。在每一行中，尝试将皇后放置在每一个位置上。 3. 检查当前位置是否与已放置的皇后冲突。如果冲突，则回溯到上一行，并尝试下一个位置。 4. 如果成功放置了8个皇后，则找到了一个解，将其保存。 5. 继续尝试下一个位置，直到所有可能的解都被找到。 四、实验结果 通过实验，我们找到了92个不同的解，符合八皇后问题的要求。这些解展示了八皇后问题的多样性，每个解都有其独特的棋盘布局。 五、实验分析 回溯法的优点在于可以找到所有解，而不仅仅是一个解。然而，在问题空间较大时，回溯法的搜索时间会变得非常长。因此，为了提高搜索效率，我们可以采用一些优化方法。 1. 剪枝操作：在搜索过程中，当发现当前位置与已放置的皇后冲突时，可以立即回溯到上一行，而不是继续尝试下一个位置。这样可以减少不必要的搜索。 2. 启发式搜索：通过引入启发函数，可以在搜索过程中优先考虑最有希望的分支，从而更快地找到解。例如，在八皇后问题中，可以优先考虑放置在当前行与已放置皇后冲突最少的位置。 3. 并行计算：对于一些复杂的问题，可以利用并行计算的优势，同时搜索多个分支，从而加快搜索速度。 六、实验总结 通过本次实验，我们深入了解了回溯法的原理和应用。回溯法是一种强大的算法解决方法，适用于各种组合优化和搜索问题。在实际应用中，我们可以根据具体问题的特点，采用不同的优化方法，以提高回溯法的效率。 然而，回溯法也有其局限性，特别是在问题空间较大时，搜索时间会变得非常长。因此，在实际应用中，我们需要权衡时间和空间的消耗，选择合适的算法和优化方法。 希望通过本次实验，大家对回溯法有了更加深入的理解，并能够灵活运用于实际问题的求解中。回溯法作为一种经典的算法思想，将在未来的科学研究和工 八皇后实验报告 八皇后实验报告 引言： 八皇后问题是一个经典的数学问题，它要求在一个8x8的国际象棋棋盘上放置8个皇后，使得任意两个皇后都不会互相攻击。这个问题看似简单，但实际上却充满了挑战。在本次实验中，我们将探索八皇后问题的解法，并通过编写算法来解决这个问题。 一、问题背景： 八皇后问题最早由数学家马克斯·贝瑟尔于1848年提出，它是一道经典的递归问题。在国际象棋中，皇后可以在同一行、同一列或同一对角线上进行攻击，因此我们需要找到一种方法，使得8个皇后彼此之间不会相互攻击。 二、解决方法： 为了解决八皇后问题，我们可以使用回溯法。回溯法是一种穷举搜索的方法，它通过逐步尝试所有可能的解决方案，直到找到符合要求的解。 具体步骤如下： 1. 初始化一个8x8的棋盘，并将所有格子标记为无皇后。 2. 从第一行开始，依次尝试在每一列放置一个皇后。 3. 在每一列中，检查当前位置是否符合要求，即与已放置的皇后不在同一行、同一列或同一对角线上。 4. 如果当前位置符合要求，将皇后放置在该位置，并进入下一行。 5. 如果当前位置不符合要求，尝试在下一列放置皇后。 6. 重复步骤3-5，直到找到一个解或者所有可能的位置都已尝试过。 7. 如果找到一个解，将其输出；否则，回溯到上一行，继续尝试下一列的位置。 三、编写算法： 基于上述步骤，我们可以编写一个递归函数来解决八皇后问题。伪代码如下所示： ``` function solveQueens(board, row): if row == 8: print(board) # 打印解 return for col in range(8): if isSafe(board, row, col): board[row][col] = 1 solveQueens(board, row + 1) board[row][col] = 0 function isSafe(board, row, col): for i in range(row): if board[i][col] == 1: return False if col - (row - i) >= 0 and board[i][col - (row - i)] == 1: return False if col + (row - i) < 8 and board[i][col + (row - i)] == 1: return False 八皇后问题代码实现 /*代码解析 */ /* Code by Slyar */ #include <stdio.h>#include <stdlib.h> #define max 8 int queen[max], sum=0; /* max为棋盘最大坐标*/ void show() /* 输出所有皇后的坐标*/{ int i; for(i = 0; i < max; i++) { printf("(%d,%d) ", i, queen[i]); } printf("\n"); sum++;} int check(int n) /* 检查当前列能否放置皇后*/{ int i; for(i = 0; i < n; i++) /* 检查横排和对角线上是否可以放置皇后*/ { /* ///题目的要求是所有皇后不在同一横排、竖排、对角线上。 1、queen[n]值为竖排号，可看为Y轴上值。 n值为横排号，可看为X轴上值。 2、(1)先从横坐标第n点排开始放皇后，再放第n+1，所有不会同一横坐标点即同一竖排。 (2)queen[i] == queen[n]时即y坐标相等，即在同一横排，此时判断不合规则点。(3)abs(queen[i] - queen[n]) == (n - i)，可变形为(queen[n] - queen[i]) /(n - i)==tan45°或tan135° 由公式可得出，点(n,queen[n])与点(i,quuen[i])在同一条左斜线 135°或右斜45°，即国际象棋上的每个格子的两条斜角线。 3、由2即可得出当前格式是否能放置一个皇后。 */ if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i)) { return 1; } } return 0;} void put(int n) /* 回溯尝试皇后位置,n为横坐标*/{ int i; for(i = 0; i < max; i++) { queen[n] = i; /* 将皇后摆到当前循环到的位置*/ if(!check(n)) { if(n == max - 1) { show(); /* 如果全部摆好，则输出所有皇后的坐标*/ } else { put(n + 1); /* 否则继续摆放下一个皇后*/ } } }} int main(){ put(0); /* 从横坐标为0开始依次尝试*/ printf("TTTTTT----%d\n", sum); //system("pause"); //while(1); return 0;} /* 算法系列---回溯算法 引言 寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不 算法设计与分析 实验报告 —八皇后问题 - 姓名：*** 学号：******** 班级：软件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++) 设计任务书 指导教师（签章）： 年月日 摘要： 众所周知的八皇后问题是一个非常古老的问题，具体如下：在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上,这是做出这个课题的基础。要求编写实现八皇后 问题的递归解法或非递归解法，对于任意给定的一个初始位置，输出八皇后问题的一个布局。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。 要求熟练运用C++语言、基本算法的基础知识，独立编制一个具有中等难度的、解决实际应用问题的应用程序。通过对题意的分析与计算，用递归法回溯法及枚举法解决八皇后是比较适合的。递归是一种比较简单的且比较古老的算法。回溯法是递归法的升华，在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而枚举法，更是一种基础易懂简洁的方法。把它们综合起来，就构成了今天的算法。不论用什么法做这个课题，重要的就是先搞清楚哪个位置是合法的放皇后的位置，哪个不能，要先判断，后放置。 关键词：八皇后；递归法；回溯法；数组；枚举法……. 目录 1 课题综述…………………………………………………………………………………………错误!未定义书签。八皇后问题概述错误!未定义书签。 预期目标错误!未定义书签。 八皇后问题课题要求错误!未定义书签。 面对的问题错误!未定义书签。 2 需求分析…………………………………………………………………………………………错误!未定义书签。涉及到的知识基础错误!未定义书签。 总体方案错误!未定义书签。 3 模块及算法设计……………………………………………………………………………………错误!未定义书签。算法描述错误!未定义书签。 ．详细流程图错误!未定义书签。 4.代码编写………………………………………………………………………………………….错误!未定义书签。 5 程序调试分析…………………………………………………………………………………….错误!未定义书签。 6 运行与测试……………………………………………………………………………………….错误!未定义书签。总结…………………………………………………………………………………………….错误!未定义书签。 致谢………………………………………………………………………………………………错误!未定义书签。参考文献……………………………………………………………………………………….错误!未定义书签。指导教师评语………………………………………………………………………………………错误!未定义书签。 4 组合优化 组合优化问题在实践中有着广泛的应用，同时也是计算机科学中的重要研究课题。本章对于八皇后问题、SAT 问题、装箱问题、背包问题及TSP 问题等五个经典的组合优化问题，给出其定义、串行算法描述、并行算法描述以及并行算法的MPI 源程序。 1.1 八皇后问题 1.1.1 八皇后问题及其串行算法 所谓八皇后问题（Eight Queens Problem ），是在8*8格的棋盘上，放置8个皇后。要求每行每列放一个皇后,而且每一条对角线和每一条反对角线上最多只能有一个皇后，即对同时放置在棋盘的任意两个皇后11(,)i j 和22(,)i j ，不允许 1212()()i i j j -=-或者 1122()()i j i j +=+的情况出现。 八皇后问题的串行解法为如下的递归算法： 算法16.1 八皇后问题的串行递归算法 /* 从chessboard 的第row 行开始放置皇后 */ procedure PlaceQueens(chessboard, row) Begin if row > 8 then OutputResult(chessboard) /* 结束递归并输出结果 */ else for col = 1 to 8 do /* 判断是否有列、对角线或反对角线冲突 */ （1）no_collision = true （2）i = 1 （3）while no_collision and i < row do （3.1）if collides(i, chessboard[i], row, col) then no_collision = false end if （3.2）i = i + 1 end while （4）if no_collision then （4.1）chessboard[row] = col /* 在当前位置放置一个皇后 */ （4.2）go(step + 1, place) /* 递归地从下一行开始放置皇后 */ end if end for end if End /* PlaceQueens */八皇后问题
八皇后实验报告
C++课程设计八皇后问题
数据结构实验报告八皇后问题
八皇后问题有多少解
人工智能实验报告,包括八数码问题八皇后问题和tsp问题
算法设计与分析---回溯实验报告
八皇后问题实验报告
数据结构与算法专题实验实验报告-八皇后-背包问题的求解-农夫过河
回溯法实验报告
八皇后实验报告
八皇后问题代码实现
算法设计与分析实验报告—八皇后问题
八皇后课程设计实验报告_C++
组合优化
相关主题
文本预览