1、数据结构课程设计 八皇后问题 2012 年 3 月 2 日 数据结构课程设计数据结构课程设计 课题课题：八皇后问题：八皇后问题 学 院：计算机科学与信息工程学院 专 业：计算机科学与技术 年 级：2010 级计本二班 数据结构课程设计 八皇后问题 2012 年 3 月 2 日 八皇后问题八皇后问题 一一 八皇后问题简述: : 八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题 是十九世纪著名的数学家高斯 1850 年提出：在 8X8 格的国际象棋上摆放八个皇 后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线 上，问有多少种摆法。 二二 解决思路：解决思路：
2、先声明我们根据条件可以知道皇后肯定是每行都有且只有一个所以我们创 建一个数组 xt让数组角标表示八皇后的行，用这个角标对应的数组值来确定 这个皇后在这行的那一列。 我们用递归来做： 这问题要求皇后所在的位置必须和其他皇后的位置不在同一行、列还有 把 两个皇后看成点其|斜率|=1；所以我们就要写这个限定条件用一个函数来实现： 函数内对每一个已经放好的皇后的位置进行判断，所以就要有个循环。 我们既然是用递归来解决问题那就要把这个问题分成一个个相同的小问题 来实现。 不难发现我们要在 8*8 的方格里放好 8 个皇后那我们就要知道在 8（列） *7（行）是怎么放的在有我们事先写好的判断函数放好最后行
3、就搞定了；以此类 推我们要知道 8*7 的怎么方的我们就要知道 8*6 是怎么样的就好了， 所以我们是 以一行怎么放作为一个单元。 我们就去建一个可以放好一行的函数 backtrack（int t）里面的 t 表示是 第几行， 在 main 函数调用的时候第一次传进来的是 0 也就是从第一行开始判断。 我们就开始写函数体了： 每一行有 8 个位置可以放，每一个位置我们都要去判断一下所以我们就用 循环来搞定。 在这个循环里面我们让 xt=i 也就是从这一行的第一个开始判断。 放好后 就要去判断是否符合条件。如果符合条件我们就在调用这个函数本身 backtrack 不过传进去的参数是 t+1 也就
4、是下一行的意思。 在进行判断下一行之前我们要判断一下 t 是不是等于 8 也就是已经是最后 一行了，如果是最后一行了我们就可以将其进行输出。打印 8*8 的矩阵（提示在 写一个函数）皇后的位置用 1 表示出来没有的用 0 表示。 三三. .组员工作分配组员工作分配: : 尹佐斌: 算法分析，代码编写，后期调试 黄文毅: 资料查找，论文设计，代码编写 檀卫杰: 算法分析，代码编写，后期调试 马赈耀: 论文设计，代码编写，后期调试 数据结构课程设计 八皇后问题 2012 年 3 月 2 日 四四 代码代码与注解与注解： #include #include #include #include #include#include #include #include /用用 getch()getch()要调用的头文件要调用的头文件 #include #include /要用要用systemsystem 函数要调用的头文件函数要调用
