八皇后问题的解决完整文档

《八皇后问题的解决完整文档》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、淮阴工学院数据结构课程设计报告设计题目：八皇后系（院）:计算机工程系专业：信息安全班级：信息106学生姓名:叶青学号:1061303127指导教师:张亚红寇海洲胡荣林夏森学年学期:2007~2008学年第2学期2008年6月25日设计任务书课题名称八皇后设计目的1.用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现．2.通过这次课程设计,提高自己的编程能力,熟悉c++的编程坏境,为以后的程序开发打下基础.实验环境1）  

2、   系统要求：win98以上操作系统；2）      语言平台：tc++或vc++6.0；3）     执行文件：八皇后.exe任务要求试编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解。工作进度计划序号起止日期工作内容12008.6.23~2008.6.24查阅相关内容22008.6.24~2008.6.25编写代码及实习报告32008.6.25~2008.6.26完善课程设计报告42008.6.26~2008.6.27答辩指导教师（签章）：2008年6月30日摘要：

3、八皇后问题要求在一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。而本课程设计本人的目的也是通过用c++语言平台将一个８＊８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击的92种结构予以实现． 使用递归方法最终将其问题变得一目了然，更加易懂。关键词：八皇

4、后;c++;递归法目录1.课题综述11.1课题的来源及意义11.2面对的问题12.需求分析12.1涉及到的知识12.2软硬件的需求12.3功能需求23.概要设计24.详细设计和实现24.1算法描述及详细流程图24.1.1算法描述34.1.2算法流程图35.代码编写及详细注释46.程序调试76.1调试过程、步骤及遇到的问题77.运行与测试77.1运行演示7总结9致谢10参考文献11.1.课题综述1.1课题的来源及意义八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。在国

5、际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。到了现代，随着计算机技术的飞速发展，这一古老而有趣的数学游戏问题也自然而然的被搬到了计算机上。运用所学计算机知识来试着解决这个问题是个锻炼和提高我自己编程能力和独立解决问题能力的好机会，可以使我增强信心，为我以后的编程开个好头

6、，故我选择了这个有趣的课题。1.2面对的问题1）   解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；2）使用数据结构的知识，用递归法解决问题。2.需求分析2.1涉及到的知识本次课程设计中，用到的主要知识有：递归法的运用，for语句的灵活运用，数据结构中树知识的灵活运用、栈及数组的掌握。2.2软硬件的需求1）系统要求：win98以上操作系统；2)语言平台：

7、tc++或vc++6.0；2.3功能需求当运行程序时，在屏幕上显示每一种方法八个皇后的相对位置，要用比较直观的界面显示。3.概要设计本课件学生是用循环递归循环来实现的，分别一一测试了每一种摆法，并把它拥有的92种变化表现出来。在这个程序中，我的主要思路以及思想是这样的：1）解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；对角线：对角线有两个方向。在这我把这

8、两条对角线称为：主对角线和从对角线。在同一对角线上的所有点（设下标为(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.详细设计和