八皇后问题实验报告递归非递归javaC语言+分析.docVIP

PAGE 23 数据结构课程设计 题目：八皇后问题 指导教师： 胡* 学生院系： 数学学院 学生班级： 信计*班 学生姓名： 黎*文 学生学号： * 2016年12月30日 目录 TOC \o 1-3 \h \u HYPERLINK \l _Toc25216 一.功能以及需求分析 PAGEREF _Toc25216 3 HYPERLINK \l _Toc3453 1.1 问题的由来和背景 PAGEREF _Toc3453 3 HYPERLINK \l _Toc32312 1.2 问题的基本解决思路 PAGEREF _Toc32312 3 HYPERLINK \l _Toc9895 1.3 问题的应用 PAGEREF _Toc9895 3 HYPERLINK \l _Toc3691 二.总体设计 PAGEREF _Toc3691 4 HYPERLINK \l _Toc282 2.1 运行环境 PAGEREF _Toc282 4 HYPERLINK \l _Toc907 2.2 程序框架 PAGEREF _Toc907 4 HYPERLINK \l _Toc9069 2.3 算法分析 PAGEREF _Toc9069 4 HYPERLINK \l _Toc27157 2.3.1 总体算法分析 PAGEREF _Toc27157 4 HYPERLINK \l _Toc3941 2.3.2 非递归算法分析 PAGEREF _Toc3941 6 HYPERLINK \l _Toc12045 2.3.3 递归算法的分析 PAGEREF _Toc12045 6 HYPERLINK \l _Toc28413 三.详细设计 PAGEREF _Toc28413 6 HYPERLINK \l _Toc10594 3.1 递归法的详细设计 PAGEREF _Toc10594 6 HYPERLINK \l _Toc18116 3.2 非递归法的详细设计 PAGEREF _Toc18116 7 HYPERLINK \l _Toc5979 四.具体实现及运行 PAGEREF _Toc5979 10 HYPERLINK \l _Toc16399 4.1 QueenMainl类的实现： PAGEREF _Toc16399 10 HYPERLINK \l _Toc30842 4.2 QueenNR类： PAGEREF _Toc30842 10 HYPERLINK \l _Toc29135 4.3 QueenRS类： PAGEREF _Toc29135 11 HYPERLINK \l _Toc12161 4.4 C语言程序： PAGEREF _Toc12161 11 HYPERLINK \l _Toc1293 五. 总结 PAGEREF _Toc1293 12 HYPERLINK \l _Toc30064 六.代码清单 PAGEREF _Toc30064 13 HYPERLINK \l _Toc14943 6.1 Java代码： PAGEREF _Toc14943 13 HYPERLINK \l _Toc11711 6.2 C语言源代码： PAGEREF _Toc11711 20 一.功能以及需求分析 1.1 问题的由来和背景 八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。 八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。 1.2 问题的基本解决思路 八皇后问题最早是由国际西洋棋棋