八皇后问题.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《八皇后问题.pdf》由会员分享,可在线阅读,更多相关《八皇后问题.pdf(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、数据结构课程设计报告八皇后问题班级:*姓名:*学号:*八皇后问题1、问题分析八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高 斯1850 提出;在 8X的国际象棋上摆放八皇后,使其不能互相攻击,即任意 两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。高斯认 为有 76 种方案。1854 年在柏林的象棋杂志上不同的作者发表了解,后人有人用图论的方法解出 92 宗结果。八皇后问题是在 8*8 的国际象棋棋盘上,安放 8 个皇后,要求没有一个皇 后能够 吃掉”任何其他一个皇后,即没有两个或两个以上的皇后占据棋盘上的 同一行、同一列或同一条对角线。八皇后在棋盘上分布的各种
2、可能的格局,其数非常大,但是可以将一些明 显不满足问题要求的格局排除掉。由于任何两个皇后不能同行,即每一行只能 放置一个皇后,因此将第 i 个皇后放置在第 i 行。这样在放置第 i 个皇后时,只 要考虑它与前i-1 个皇后处于不同列和不同对角线位置上即可。2、算法描述40 种不同的从第一行起逐行放置皇后,每放置一个皇后均需要依次对第1, 23 列进行试探,并尽可能取小的列数。若当前试探的列位置是安全的,即不与已经放置的其他皇后冲突,则将该行的列位置保存在栈中,然后继续在下一行上寻找安全位置;若当前试探的列位置不安全,则用下一列去试探,当 8 列位置试探完 毕都未找到安全位置时,就退栈回溯到上一
3、行,修改栈顶保存的皇后位置,然 后继续试探。该算法抽象的描述如下:(1)置当前行当前列均为 1;(2)While (当前行号 v = 8);(3)检查当前行,从当前列起逐列试探,寻找安全列号;(4)if (找到安全列号)(5)放置皇后,将列号放入栈中,并将下一行置为当前行,第 1 列置为当 前列;(6)else(7)退栈回溯到上一行,移去该行已经放置的皇后,已该皇后所在列的下一列作为当前列;(8)2. 1 算法求精要对上述抽象算法进行逐步求精,就需要确定相应的存储结构和有关的数据类型。当前行和列分别用 i 和 j 表示;用数组 s1昧示顺序栈,栈空间的下 标值表示皇后所在的行号,栈的内容是皇后
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 皇后 问题
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内