数据结构课程设计

题目：八皇后问题

指导教师： 胡*

学生院系： 数学学院 学生班级： 信计*班 学生姓名： 黎*文 学生学号： 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