八皇后问题的解决完整

■ •・・ 1 ■ ■ ■ WAS Standardization ofsany group #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN#

数据结构课程设计报告

设计题目： __________ 八 皇 后 _______________________________________

2008 年 6 月25 日

设计任务书

课题 八 名称 皇 后 1. 用C++语言平台将一个8 * 8的棋盘上放上8个皇后，使得每一个 皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92 种结构予以实设计 现. 目的 2. 通过这次课程设计,提高自己的编程能力，熟悉C++的编程坏境，为以 后的程序开发打下基础. 1） 系统要求：win98以上操作系统； 实验 2） 语言平台：tc++或vc++； 环境 3）执行文件：八皇后.exe 任务 试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算 法，并给出所有的解。 要求 工作进度计划 序号 起止日期 工作内容 1 查阅相关内容 2 编写代码及实习报告 3 完善课程设计报告 4 指导教师（签章）：

答辩 2008 年6 月 30 日

摘要:

八皇后问题要求在一个8 * 8的棋盘上放上8个皇后，使得每一个皇后既 攻击不到另外七个皇后，也不被另外七个皇后所攻击.按照国际象棋的规则， 一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子.因 此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或 同一斜线上。

而本课程设计本人的目的也是通过用C++语言平台将一个8 * 8的棋盘上放上 8个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所 攻击的92种结构予以实现.使用递归方法最终将其问题变得一目了然，更加 易懂。

关键词：八皇后；C++ ;递归法

1. 课题综述

1. 1课题的来源及意义

八皇后问题是一个古老而着名的问题，该问题是十九世纪着名的数学 家高斯

1850年提出的。

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

到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问 题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问 题是个锻炼和提高我白己编程能力和独立解决问题能力的好机会，可以使我 增强信心，为我以后的编程开个好头，故我选择了这个有趣的课题。

1. 2面对的问题

1）解决冲突问题：

这个问题包括了行，列，两条对角线；

列：规定每一列放一个皇后，不会造成列上的冲突；

行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇 后，要把以I为下标的标记置为被占领状态;

2）使用数据结构的知识，用递归法解决问题。

2. 需求分析

2. 1涉及到的知识

本次课程设计中，用到的主要知识有：递归法的运用，for语句的灵活

运用，数据结构中树知识的灵活运用、栈及数组的掌握。

2. 2软硬件的需求

1） 系统要求：win98以上操作系统；

2） 语言平台：tc++或vc卄；

2. 3功能需求

当运行程序时，在屏幕上显示每一种方法八个皇后的相对位置，要用比 较直观的界面显示。

3. 概要设计

本课件学生是用循环递归循环来实现的，分别一一测试了每一种摆法， 并把它拥有的92种变化表现出来。在这个程序中，我的主要思路以及思想 是这样的：

1）解决冲突问题：

这个问题包括了行，列，两条对角线;

列：规定每一列放一个皇后，不会造成列上的冲突;

行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇 后，要把以I为下标的标记置为被占领状态；

对角线：对角线有两个方向。在这我把这两条对角线称为：主对角线和 从对角线。在同一对角线上的所有点（设下标为（i,j））,要么（i+j）是常 数，要么

（i-j）是常数。因此，当第I个皇后占领了第J列后，要同时把以 （i+j）、（i-j）为下标的标记置为被占领状态。

2）数据结构的实现

而对于数据结构的实现，学生则是着重于：

数组a[I]： a [I]表示第I个皇后放置的列；I的范围：1..8;

对角线数组：b[j]（主对角线），c[j]（从对角线），根据程序的运行， 去决定主从对角线是否放入皇后；

4. 详细设计和实现

4. 1算法描述及详细流程图

算法描述

A、 数据初始化。

B、 从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇

后的要求），先测试当前位置（n, m）是否等于0 （未被占领）。如果是, 摆放第n个皇后，并宣布占领（记得姚横列竖列斜列一起设置），接着进行 递归；如果不是，测试下一个位置（n, m+1）,但是如果当n〈二8, m=8时， 发现此时已无法摆放时，便要进行回溯。从问题的某一种可能出发，搜索从 这种情况能出发，继续搜索，这种不

断“回溯”的寻找解的方法，称为“回 溯法”。

C、 使用数组实现回溯法的思想。

D、 当n>8时，便打印出结果。

E、 输出函数我使用printf输出，运行形式为：第m种方法为：* * *

算法流程图

5. 代码编写及详细注释

ttinclude <>

ttinclude <>

ttinclude <>

ttinclude <>

ttinclude <>

ttdefine QUEENS 8 int iCount = 0; -5d\" , ++iCount);程序调试

6. 1调试过程、步骤及遇到的问题

在完整程序调试时遇到儿个小问题，后经细心改正后才把调试工作做 完。

例如：当用printf输出时，出现了一些错误，儿经调试后，发现原來是缺 少了这样一个头文件，添加了头文件后，还出现了一些问题，逻辑错误导致程 序死

循环或不循环或循环一小部分，但是编译时却没有错误，就是没有正确的 输出答案，一开始我也不知道是怎么回事，通过和同学的交流，发现是逻辑错 误，经过改正后，程序终于可以运行了.

7. 运行与测试

运行演示

总 结

通过了 19周这个星期的程序设计，我从中得到了许多的经验以及软件设 计的一些新的思路；从这个八皇后问题设计以及分析中，本人从中理解到了数 据结构对于计算机软件设计的重要性，它的使用，可以改变一个软件的运行周 期，也可以将软件的思路从繁化简，并且都能够通过数据结构的相关引导，将 本身以前编程思想进行扩充，发展；这也是在这次课程设计中我所掌握得到 的。

但由于我的基本知识还不是那么扎实，也缺乏对软件设计的经验，在这过 程中也出现了一些问题，如，八皇后在变成初期由于没真正体会到数据结构中

“树”在里面的运用，将程序往大一时c语言的方向发展，不自觉的采用了非 递归的算法，结果大大增加了程序的复杂程度。并且也让整个程序的时间复杂 度变得更大；在后来学生对数据结构的第六章进行了比较深入的研读，才发现 了数据结构树的实际运用的空间是相当的大，并且，通过了重温树的回溯，以 及二叉树的遍历，最终将程序进行了一次较大的改造。并且通过思考，再将以 前的数组知识加以运用才最终解决了这个问题，整个程序的算法的可看性也有 了相当的改进。

课程设计随着时间的推移，也即将结束了，但这个学期数据结构的学习还 是具有相当大的意义，它从一个程度上改变了我们的编程思想，如何将一个程 序快速而又准备的进行编写，进行编译，都成为了我们思考的重点，也通过这 一个学期的学习，我们将数据结构的思想带入到了我们以后的编程学习中去。 在这个阶段，我也明白了，好的思想，

不能提留于字面上的认知，还需要的是 平时多练多写一些相关的程序，并且通过修改，加入新的算法去尝试改变自己 的一些编程思想。保持更新算法的速度，这才是关键。

课程设计己经接近尾声了，但它给我的不只是程序设计上的满足，更重要 的是对自己编程思想的一次更新，以及对算法的一个全新的认识！

我觉得还可以考虑开发N皇后问题,在主界面中添加一个int型的变量, 程序一开始要求输入一个数（确定是儿皇后问题），输入后按下enter后，输出 各种解.主程序与八皇后的求解大体相同.

致 谢

在这次课程设计中，我遇到了不少问题，包括程序上的和课程设计的撰写上 的，同学曾给过我许多帮助，在此我表示对他们的忠心感谢。同时，指导老师和 实验人员给了我很多上机的机会，给了我一个做课程设计的很好的条件，我才 能够顺利的完成，在此，我仅以文字的形式表示忠心感谢，感谢他们这么多天 对我的帮助。

参考文献

[1] 苏仕华，数据结构课程设计.-北京:机械工业出版社，

[2] 于永彦，赵建洋.课程设计指导书.淮安：江苏淮阴工学院计算机工程

系,2006

[3] 刘振安，刘燕君，孙忱•.北京：高等教育出版社,2003

[4] 陈志泊，张海燕，王春玲..中国铁道出版社，2005

[5] 吕凤哲,C++语言程序设计（第二版）•北京：电子工业出版社,2005

[6] 殷人昆，陶永雷等.数据结构（用面向对象方法与C++ ）.北京:清华大 学出版

社，1999

[7] 严蔚敏，吴伟民，数据结构.北京：清华大学出版社，1997

[8] 李春葆.数据结构一考研指导.北京:清华大学出版社,2002

[9] 陈慧南.数据结构一C++语言描述.北京：人民邮电出版社，指导教师评语 2005. 03

学号 27 姓名 叶青 班级 信息106 选题 八 名称 皇 后 权重 序号 评价内容 (%) 得分 1 考勤记录、学习态度、工作作风与表现。 5 自学情况： 2 上网检索机时数、文献阅读情况(笔 记)。 10 论文选题是否先进，是否具有前沿性或前 瞻3 性。 5 成果验收： 4 是否完成设计任务；能否运行、可操 作性如何等。 20

报告的格式规范程度、是否图文并茂、语 言规范及流畅程度；主题是否鲜明、重心 是否突出、论述是否充分、结论是否正 确；是否提出了自己的独到见解。 5 30 6 文献引用是否合理、充分、真实。 5 答辩情况： 自我陈述、回答问题的正确性、用语 准7 确性、逻辑思维、是否具有独到见解 等。 25 合计

指导教师（签章）：

2008 年 6 月 30 口