数据结构课程设计-四、八、N皇后问题

计算机与软件工程学院 课程设计说明书

课 程 名 称: 数据结构与算法-课程设计 课 程 代 码: 106014389 题 目: 四、八、N皇后问题 年级/专业/班: 学 生 姓 名: 学 号: 312012080611523 开 始 时 间: 年 月 日 完 成 时 间: 年 月 日 课程设计成绩：

学习态度及平技术水平与实际时成绩（30） 能力（20） 创新（5） 说明书撰写质量（45） 总 分（100） 指导教师签名： 年 月 日

1

八皇后问题

摘 要

解决八皇后问题主要利用了递归法、回溯法,以及对for语句、数据结构中树的灵活运用、和对栈及数组的掌握。编程实现了在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面。编程实现了任意给定一个初始位置，输出八皇后问题的一个布局。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。

关键词：递归法; 回溯法; 顺序栈；数组；

2

八皇后问题

目 录

1需求分析 ...................................................................................................................................................... 4 2开发及运行平台 .......................................................................................................................................... 5 3 概要设计 ..................................................................................................................................................... 6 4 详细设计 ..................................................................................................................................................... 8 5 调试分析 ..................................................................................................................................................... 9 6 测试结果 ................................................................................................................................................... 10 6.1 遇到的问题 ........................................................................................................................................... 10 6.2 调试结果 ............................................................................................................................................... 10

.......................................................... 11

7 结论 ........................................................................................................................................................... 12 通过这次的课程设计，让我了解了八皇后这一经典的问题。同时让我更好地掌握了栈思想以及一维数组等等知识,以及一些书本上没有的东西，这对我以后的学习生涯以及将来步入社会起到很大的帮助。这次课程设计虽然花了我很多时间和精力，但很值得,因为它对我能力提高起到很大帮助。这次课程设计也提醒我以前知识的匮乏,它给我敲响了警钟,让我意识到自己基础的不扎实.当然这次实验还是有很多问题的。比如程序设计的界面不够好，一些程序并非自己所写,而是修改某些程序而成,但这些不该,在下次课程设计时不会再发生。 ......................................................................................... 12 参考文献 ....................................................................................................................................................... 13 附 录 ......................................................................................................................................................... 14

3

八皇后问题

1需求分析

八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。

在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有92个解答。

本次课设要求指定任一初始位置，即可输出八皇后问题的所有行列布局。拓展完成四皇后问题。

4