文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 数据结构与算法中的“递归”——用回溯法求解8皇后问题
侵权投诉

数据结构与算法中的“递归”——用回溯法求解8皇后问题

回溯法解决8皇后问题

八皇后问题是一个古老而著名的问题,它是回溯算法的典型例题。该问题是十九世纪德国著名数学家高斯于1850年提出的:在8行8列的国际象棋棋盘上摆放着八个皇后。若两个皇后位于同一行、同一列或同一对角线上,则称为它们为互相攻击。在国际象棋中皇后是最强大的棋子,因为它的攻击范围最大,图6-15显示了一个皇后的攻击范围。

数据结构与算法中的“递归”——用回溯法求解8皇后问题

图6-15 皇后的攻击范围

现在要求使这八个皇后不能相互攻击,即任意两个皇后都不能处于同一行、同一列或同一对角线上,问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。现代教学中,把八皇后问题当成一个经典递归算法例题。图6-16显示了两种八个皇后不相互攻击的情况。

第1页

你可能喜欢

热门文档

相关文档

  • 数据结构课程设计 回溯法解决8皇后n皇后问题

    数据结构课程设计 回溯法解决8皇后n皇后问题_工学_高等教育_教育专区。回溯法解决8皇后n皇后问题数据结构课程设计 学院: 专业: 姓名: 学号: 信息科学技术学院 ...

  • 数据结构与算法专题实验实验报告_八皇后_背包问题的求...

    数据结构与算法专题实验实验报告_八皇后_背包问题的...再 递归求解在第 i+1 行布放棋子; 若该棋子布...2.实现提示 实现提示 可利用回溯法的设计思想来解决...

  • 递归法解八皇后问题

    递归法解八皇后问题_IT/计算机_专业资料。递归法...递归实现 n 皇后问题 算法分析: 数组 a、b、c ...则回溯,重置 Queen[i][iColumn]='*'; a[...

  • 八皇后问题数据结构课程设计报告

    通过对题意的分析与计算,用递归法回溯法及枚举法解 决八皇后是比较适合的。递归是一种比较简单的且比较古老的算法。回溯法是递归法 的升华,在用来求问题的所有解...

  • 数据结构八皇后问题

    本程序通过对子函数 void qu(int i)的调用,将八皇后的问题关键通过数据结构的...然后再通过回溯法进行设计, 回溯法是设计递归过程的一个重要的方法。它的求解...

  • 八皇后问题的最佳解决方案 123

    本文主要描述递归回溯与非递归回溯,并用这两个算法 ...算法,当然最经典的解决八皇后问题的算法是 回溯法,...参考文献 [1] 严蔚敏,吴伟民.数据结构.北京:清华...

  • 数据结构课程设计 八皇后问题

    通过对题意的分析与计算 ,用递归法回溯法及枚举法解决八皇后是比较适合的 。递归是一种比较简单的且比较古老的算法 。回溯法是递归法的升华 ,在用来求问题的所有...

  • 递归与回溯法

    递归法和回溯法 5页 免费 数据结构与算法中的“递归... 8页 2财富值 #... 递归与回溯算法 70页 免费 回溯法解决n皇后问题 5页 2财富值 回溯法之N...

  • _8皇后问题_与回溯法

    数据结构与算法中的“递... 8页 1下载券 回溯法解八皇后问题 3页 免费 ...问题的方法——图 1 是一个 4×4 的棋盘,现将第 1 个皇后 放入第 1 行...

  • 数据结构课程设计之 八皇后问题

    数据结构课程设计之 八皇后问题_信息与通信_工程...八皇后问题是一个古老而著名的问题,是回溯算法的...如果没有出现攻击,在第 j 列安放的皇后不动,递归...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email