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

数据结构课程设计

题目:八皇后问题

指导教师: 胡*

学生院系: 数学学院 学生班级: 信计*班 学生姓名: 黎*文 学生学号: 14070204**

2016年12月30日

1

目录

一.功能以及需求分析................................................................................................... 3

1.1 问题的由来和背景......................................................................................... 3 1.2 问题的基本解决思路..................................................................................... 3 1.3 问题的应用..................................................................................................... 3 二.总体设计................................................................................................................... 4

2.1 运行环境......................................................................................................... 4 2.2 程序框架......................................................................................................... 4 2.3 算法分析......................................................................................................... 4 2.3.1 总体算法分析............................................................................................. 4 2.3.2 非递归算法分析......................................................................................... 6 2.3.3 递归算法的分析......................................................................................... 6 三.详细设计.................................................................................................................. 6

3.1 递归法的详细设计......................................................................................... 6 3.2 非递归法的详细设计..................................................................................... 8 四.具体实现及运行..................................................................................................... 10

4.1 QueenMainl类的实现:.............................................................................. 10 4.2 QueenNR类:................................................................................................ 10 4.3 QueenRS类:................................................................................................ 11 4.4 C语言程序:................................................................................................ 11 五. 总结....................................................................................................................... 12 六.代码清单................................................................................................................. 13

6.1 Java代码:.................................................................................................. 13 6.2 C语言源代码:............................................................................................ 20

2

一.功能以及需求分析

1.1 问题的由来和背景

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种计算机语言可以解决此问题。

八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n×n,而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。

1.2 问题的基本解决思路

八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究,其中包括高斯和康托,并且将其推广为更一般的n皇后摆放问题。八皇后问题的第一个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年,S.冈德尔提出了一个通过行列式来求解的方法。

八皇后问题出现在1990年代初期的著名电子游戏第七访客中。设置一个三维数组,第一个下标是皇后的行坐标,第二个下标是皇后的列坐标,第三个下标是残卷号。相当于有N张叠在一起的8*8棋盘,每张棋盘只在复制前面棋盘及皇后后加放置一个皇后。直到放满8皇后后才是一张完整的8皇后图,称完卷。这里实际操作时多加一行多加一列即第0行第0列,但这一行/列不作输出,只是作此行/列有无皇后的参考。

总的来说现在解八皇后问题的总体算法都是采用回溯法,也叫作穷搜法,再穷搜的时候去掉分支,减少不必要的运算,对于八皇后问题的求解,一般只能做出15皇后问题,有部分算法高手在有精良设备的情况下算出了25皇后的解。受算法和硬件计算能力的影响,因为计算量为O(n!),而且回溯法使用的内存空间特别大,所以此问题的求解还有很多可以探究的地方,尤其是算法上的改进。

1.3 问题的应用

八皇后问题可以用来解决地图的着色问题,以及迷宫的求解问题,同时,八皇后问题是一个典型的回溯法求解问题,可以用它来类比很多和回溯法有关的问题。对于现在的DNA序列问题也可以从中得到启发。

3

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4