数据结构实验报告-八皇后问题

1、2007级数据结构实验报告实验名称： 实验二栈和队列学生姓名： 班 级： 班内序号： 学 号： 日 期： 2021年11月18日1实验要求通过选择下面五个题目之一进行实现，掌握如下内容：Ø 进一步掌握指针、模板类、异常处理的使用Ø 掌握栈的操作的实现方法Ø 掌握队列的操作的实现方法Ø 学习使用栈解决实际问题的能力Ø 学习使用队列解决实际问题的能力利用栈结构实现八皇后问题。八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法

2、打印所有可能的摆放方法。提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析2.1 存储结构 采用栈存储，其结构图如下:2.2 关键算法分析函数原型： bool check(int i); 2.2.1.1.1自然语言：检测至第i行所摆放的第i个皇后是否和之前的i-1个皇后发生冲突。如是，那么返回0；反之，那么当前布局合法，返回1。判断两个皇后是否相互攻击的准那么是：假设两个皇后处于同一行，或处于同一列，或处于同一斜线，就能相互攻击。基于如上准那么，函数check( )的工作原理是：考虑到数组的每个元素分别代表不同行的皇后

3、，即每行只放置了一个皇后，所以不必考虑“同处一行相互攻击的情形；对于同处一列，那么语句：if(queens=queent)就能判断出不同行的两个棋子是否同处一列；对于处于同一斜线的这种情况，首先，我们看出国际象棋的棋盘是一个八行八列的正方形。因此我们可将棋盘想象为数学上的笛卡尔平面坐标系，两颗棋子想象为平面上的两个点，就很容易发现，为保证两颗棋子不处于同一斜线，只要过这两个点的直线斜率不为1或-1，就能到达要求。由此可使用以下语句：if( abs(t-s) = abs(queens-queent) )其中t和s分别代表不同行的两个皇后，即数组queen8里不同下标的两个元素。2.1.1.1.2

4、伪代码：第j行j是第i行之前的i-1行中的一行进行操作 如果第j行放置皇后的位置和第i行相同或者第j行放置皇后的位置与第i行的皇后在斜率为1或-1的直线上，那么返回01.2否那么，返回12.2.1.2放置新棋子假设前i-1行的皇后棋子已被合法布置，现从第i行开始合法地摆放新棋子。如果当前的行数i已经大于等于8，那么在总数上加1并输出当前的棋盘布局；否那么将第i行的皇后放置在第j列,检查当前布局是否合法，如果合法，那么进入下一行，开始放置第i+1行的皇后；否那么，移去刚刚放置在第i行的皇后，重新放置该位置的皇后。.2伪代码：i大于等于8，那么输出当前的棋盘布局2.放置新的皇后i行放置皇后2.2如

5、果合法，那么继续放置下一行的皇后2.3如果不合法，移去刚刚放置的皇后2.2.2 代码详细分析检测是否冲突1如果第j行放置皇后的位置和第i行相同或者第j行放置皇后的位置与第i行的皇后在斜率为1或-1的直线上，那么返回0 if(queenj=queeni|(i-j)=abs(queeni-queenj)return 0;2. 否那么，返回1。return 1放置新棋子1.如果行数i大于等于8，那么输出当前的棋盘布局 num+; for(int i=0; i<8; i+) for(int j=0; j<8;j+) if(j=queeni) cout<<"Q"

6、; else cout<<"" cout<<endl; cout<<endl;2. 在第i行放置皇后queeni=j;3. 如果合法，那么继续放置下一行的皇后if(check(i) trial(i+1);4. 如果不合法，移去刚刚放置的皇后queeni=-1;算法的时间复杂度、空间复杂度N皇后的时间复杂度为Onn，空间复杂度为S3. 程序运行结果流程图如下开始:开始放置第一行的皇后检测是否放置满如果放满如果未放满放置新的皇后输出当前棋盘的布局检测是否冲突如果冲突，移走刚刚放置的皇后。如果不冲突，继续放置下一行的皇后3.2 测试条件：输出八皇后所有可能的情况及一共有多少种情况3.3 测试结论经检验结果正确，证明该算法是正确的。4. 总结4.1 调试时出现的问题及解决方法输出棋盘的布局时换行出现问题。经检查，在适宜的位置加了cout<<endl;后，成功的输出了棋盘的布局。4.2 心得体会回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的根本思想是：从一条路往前走，能进那么进，不能进那么退回来，换一条路再试。回溯法是计算机科学里的常用方法，使用回溯、递归，可以将很复杂的问题在形式上予以简化，以经典的“高斯八皇后为例，