--八皇后问题--回溯算法_第1页
--八皇后问题--回溯算法_第2页
--八皇后问题--回溯算法_第3页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

八皇后问题 问题描述 八皇后问题是一个古老而著名的问题 是回溯算法的典型例题 该问题是十九世纪著 名的数学家高斯 1850 年提出 在 8 8 格的国际象棋上摆放八个皇后 使其不能互相攻击 即任意两个皇后都不能处于同一行 同一列或同一斜线上 问有多少种摆法 高斯认为有 76 种方案 1854 年在柏林的象棋杂志上不同的作者发表了 40 种不同的解 后来有人用图 论的方法解出 92 种结果 问题分析 所谓回溯就是走回头路 该方法是在一定的约束条件下试探地搜索前进 若在前进中 受阻 则回头另择通路继续搜索 为了能够沿着原路逆序回退 须用栈保存曾经到达的每 一个状态 栈顶的状态即为回退的第一站 因此回溯法均可用栈来实现 现在我们利用回 溯算法求出其中一种解 其算法的基本思想如下 从第一行起逐行放置皇后 每放置一个皇后均要依次对第 1 2 8 列进行试 探 并尽可能取小的列数 若当前试探的列位置是安全的 即不与已放置的其他皇后冲突 则将该行的列位置保存在栈中 然后继续在下一行上寻找安全位置 若当前试探的列位置 不安全 则用下一列进行试探 当 8 列位置试探完毕都未找到安全位置时 就退栈回溯到 上一行 重新对下一列进行试探 直到找到问题的解 图 1 为八皇后问题的一种解 怎样判断一个位置是安全的 为解决这个问题 我们对棋盘进行分析 将棋盘横坐标 定为 i 纵坐标定为 j i 和 j 的取值范围是从 到 当某个皇后占了位置 i j 时 在这 个位置的垂直方向 水平方向和斜线方向都不能再放其它皇后了 用语句实现 可定义如 下三个整型数组 a 8 b 15 c 24 其中 各数组的代表的意义如下 程序实现 程序清单如下 include int a 8 b 15 c 24 int sit 8 记录 8 个皇后所在列 并且起到栈的作用 void EightQueen void int i j i 1 从第一行开始 试探每个皇后的位置 j 1 从第一列开始试探 while i 8 while j 8 if a j 1 b i j 2 c i j 7 3 在当前列上寻找安全位置 break j if j 8 为第 i 个皇后找到了安全位置 a j 1 0 b i j 2 0 c i j 7 0 皇后移入位置 i j sit i 1 j 相当于位置 i j 进栈 i 为下一个皇后寻找位置 j 1 else 未找到安全位置 i j sit i 1 出栈 回溯到上一行 a j 1 1 b i j 2 1 c i j 7 1 移去位置 i j 上的皇后 j j 1 从下一列继续探索 for i 1 i 8 i 输出第 i 个皇后所在的列位置 printf 1d 1d i sit i 1 printf n int main void int i for i 0 i 7 i a i 1 for i 0 i 14 i b i 1 for i 0 i 23 i c i 1 EightQueen return 0 程序运行结果 1 1 2 5 3 8 4 6 5 3 6 7 7 2 8 4 上面的程序采用了非递归方法寻找八皇后问题的一种解 要找到八皇后问题的所有解 可通过修改函数 EightQueen 使其找到一个解后 程序并不终止 而是打印输出解的信息 然后退栈回溯 继续寻求下一个解 一旦当前行是第 1 行又仍需退栈回溯时 算法终止 八皇后问题也可采用递归实现 下面的程序是采用递归方法求解八皇后问题的所有解 的源程序 include int a 8 b 15 c 15 i int sit 8 void EightQueen int i int j for j 1 j 8 j if a j 1 b i j 2 c i j 7 3 如果第 i 列第 j 行为空 a j 1 0 b i j 2 0 c i j 7 0 占用第 i 列第 j 行 sit i 1 j if i 8 EightQueen i 1 else 输出一组解 for int k 1 k 9 k printf 1d 1d k sit k 1 printf n a j 1 1 b i j 2 1 c i j 7 1 int main void for i 0 i 7 i a i 1 for i 0 i 14 i b i 1 for i 0 i 14 i c i 1 EightQueen 1 调用递归函数 return 0 列上有皇后表示第 列上无皇后表示第 j j ja

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论