八皇后设计报告.docx

安徽建筑大学
课程设计报告

课程名称: 数据结构与算法课程设计
题目: 八皇后求解
院系:
专业:
班级:
学号:
姓名:
时间:

目录
一、 绪论 2
二、 需求分析 2
三、 概要分析 2
四、 详细设计 4
五、 调试分析 5
六、 测试结果 5
七、 使用说明 6
八、 参考文献 7
绪论
八皇后问题是一个古老而著名的问题。这个问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。例如:
0
0

0
0
0
0
0
0
面对这个问题,要放在以往可能就要耗费大量的时间在纸上画来画去,这样做的耗费了大量的精力,但是效果却不佳。借助计算机就可以很高效的完成这些工作。那么,采用什么样的数据结构和算法,才能在时间和空间复杂度上完成这个问题呢?
需求分析
:
在8×8的国际象样棋盘上,放置8个皇后,使得这8个棋子不能互相被对方吃掉。
既要满足以下条件:



, 然后将这些结果输出。
3. 测试数据
输入皇后的个数8,程序会输出可能的结果,以及统计结果。
概要分析
算法思想
如果进行遍历,不仅需要遍历8*8*8*8*8*8*8*8*8 = 2^24次数据,还要判断各种条件,实际的计算复杂度还要比较这个高。其实这中间很多的计算其实很多是不需要的,因为如果我们在某一行没有可以插入的数据的话,那么这后面的
行其实就不用考虑了。也就是说,我们只有在保证前面插入的物体都合法有效的情况下,才能进行下一次的物体插入。
具体步骤如下:
(1)在第n行寻找可以插入的位置,中间涉及到位置合法性的判断
(2)如果没有可以插入的位置,返回
(3)如果有可以插入的位置, 插入数据。此时再判断是否已经是最后一行,如果是,打印输出返回;反之继续对下一行数据进行试探处理。

(1)int EightQueen[8] 表示棋盘,长度为八的int型数组,分别表示了棋盘的八行。例如EightQueen[0]的值为1,则表示第一行的第二个位置安排了棋子,同理如果EightQueen[1]的值为2,则表示第二行的第三个位置安排了棋子。
(2)typedef struct node
{
int queen[8];
int gcount;
struct node *next;
}LNode,*LinkList;
定义了一个保存所有找到的放置方法的链表,int gcount用于计数。
(3)设计概要
如下图所示:
主函数(main)
显示到终端(print)
八皇后行遍历
(e_queen)
位置合法性检查(Check)
菜单函数(menu)
写入文件(write_file)
保存链表
(add_LinkList)
详细设计
主要的程序代码
插入点合法性检