八皇后问题实验报告 递归 非递归 java C语言 +分析

《八皇后问题实验报告 递归 非递归 java C语言 +分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计题目：八皇后问题指导教师：胡*学生院系：数学学院学生班级：信计*班学生姓名：黎*文学生学号：14070204**2016年12月30日23目录一.功能以及需求分析31.1问题的由来和背景31.2问题的基本解决思路31.3问题的应用3二.总体设计42.1运行环境42.2程序框架42.3算法分析42.3.1总体算法分析42.3.2非递归算法分析62.3.3递归算法的分析6三.详细设计63.1递归法的详细设计63.2非递归法的详细设计7四.具体实现及运行104.1QueenMainl类的实现：104.2QueenNR类：104.3QueenRS类：11

2、4.4C语言程序：11五.总结12六.代码清单136.1Java代码：136.2C语言源代码：2023一.功能以及需求分析1.1问题的由来和背景八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。八皇后问题是一个以国际象棋

3、为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n=1或n≥4时问题有解。1.2问题的基本解决思路八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的

4、人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法。八皇后问题出现在1990年代初期的著名电子游戏第七访客中。设置一个三维数组，第一个下标是皇后的行坐标，第二个下标是皇后的列坐标，第三个下标是残卷号。相当于有N张叠在一起的8*8棋盘，每张棋盘只在复制前面棋盘及皇后后加放置一个皇后。直到放满8皇后后才是一张完整的8皇后图，称完卷。这里实际操作时多加一行多加一列即第0行第0列，但这一行/列不作输出，只是作此行/列有无皇后的参考。总的来说现在解八皇后问题的总体算法都是采用回溯法，也叫作穷搜法，再穷搜的时候去掉分支，减少不必要的运算，对于八皇后问题的求解，一

5、般只能做出15皇后问题，有部分算法高手在有精良设备的情况下算出了25皇后的解。受算法和硬件计算能力的影响，因为计算量为O(n!)，而且回溯法使用的内存空间特别大，所以此问题的求解还有很多可以探究的地方，尤其是算法上的改进。1.3问题的应用八皇后问题可以用来解决地图的着色问题，以及迷宫的求解问题，同时，八皇后问题是一个典型的回溯法求解问题，可以用它来类比很多和回溯法有关的问题。对于现在的DNA序列问题也可以从中得到启发。23二.总体设计2.1运行环境（1）编译环境：JDK1.8，以及eclipse，Mars4.5.2，VisualC++6.0（2）电脑系统：Win

6、dowsserver200332位（3）编译语言：Java，C语言2.2程序框架（1）MainQueen：实现可视化界面，可以选择递归和非递归两种算法得到八皇后问题的解，并将答案打印出来。（2）QueenNR：采用非递归方法求解问题。（3）QueenRS：采用递归方法求解问题。（4）编译C语言程序。2.3算法分析2.3.1总体算法分析算法的核心是回溯法，也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能

7、可以获得最终解时，则撤销当前的这一步求解过程，回溯到上一步寻找其他求解路径。为了能够撤销当前的求解过程，必须保存上一步以来的求解路径。当撤销之后满足条件，就一直做下去，直到试探完所有的可能解。总结如下：(1)设置初始化的方案（给变量赋初值，读入已知数据等）。(2)变换方式去试探，若全部试完则转(7)。(3)判断此法是否成功（通过约束函数），不成功则转(2)。(4)试探成功则前进一步再试探。(5)正确方案还未找到则转(2)。(6)已找到一种方案则记录并打印。(7)退回一步（回溯），若未退到头则转(2)。(8)已退到头则结束或打印无解另外一个关键就是对于每一个部分解

8、的判定，可归纳问题的条件