案例十八八皇后问题.

《案例十八八皇后问题.》由会员分享，可在线阅读，更多相关《案例十八八皇后问题.（40页珍藏版）》请在金锄头文库上搜索。

1、目录退出目录 案例十八 八皇后问题 本案例知识要点 数组的使用 回溯算法的使用 类的设计和使用 1页 共40页 目录退出目录 一、案例需求 案例描述 八皇后问题是1850年由数学家高斯提出来的，该 问题在88的国际象棋棋盘上放置8个皇后，条件 是做到没有一个皇后能“吃掉”任何其他皇后，即 没有任何两个皇后被放置在棋盘的同一行、同一 列或同一对角线上。 本案例利用回溯算法穷举出该问题的所有解。 案例效果图 本案例效果如图所示。 2页 共40页 目录退出目录 八皇后问题案例效果图 3页 共40页 目录退出目录 功能说明 利用回溯算法穷举出八皇后问题的 所有的解。 程序结束后，采用图形化方式顺序 输

2、出所有的可能的解，即对于每一 个解都要画出一个“棋盘”，其中“Q” 代表皇后的位置。 4页 共40页 目录退出目录 二、案例分析 八皇后问题具有这样的性质：解决问题要分若干步，每步 有几种可能的求解路线，当一种可能路线求解不成功时， 需要回头再试另一种，直到最后某条路线达到目标而解决 整个问题。如果各种路线都不成功，则说明问题不存在解 。可以使用回溯算法的基本思想来解决此问题。 先将棋盘初始化，刚开始将8个皇后都放在棋盘的外列， 即第9列，并照此对结果数组进行初始化。然后从头开始 一行一行地解决问题，从每一行的第一列开始扫描。如果 在第I行找到了合适位置，则存储到solutionI-1中，然后

3、 看下一行，即第I+1行，如果在第I+1行找到了合适位置， 则存入数组solutionI中，如果第I+1行没有合适的位置， 那就说明上一行（第I行）皇后的位置不当。此时，就应 该重新调整上一行（第I行）皇后的位置，然后再判断第I 行的后续列有没有合适的位置，这就是回溯的含义。如果 按照这个顺序成功地安排好了全部的行，就说明得到了一 套完整的解。 5页 共40页 目录退出目录 有了一个完整的解后，如果保留前七行的皇后位置 不动，考虑将最后一行的皇后挪动到其他位置，看 看是否也是合适的解，如果可以，显然这就是另外 一套解。该套解和前面的解的区别就是只有最后一 行不同。也就是说，保持棋盘的初始值为“

4、前一套解 ”，从最后一行开始向后面的列挪动“皇后”，试探其 他的解，如果最后一行没有合适的位置，就上推一 行。据此思路，直到从后向前回溯到第一行，则所 有的解就都找到了。 找第一套解与找其他的解，回溯的算法和思想基本 相似。区别在于，找第一套解时，棋盘初始状态是 皇后在棋盘外面，在第9列，从第一行开始从上到 下扫描。而找其他解的时候，棋盘的初始状态是其 他的解，从最后一行开始由下到上开始扫描。 6页 共40页 目录退出目录 7页 共40页 目录退出目录 使用回溯算法要解决两个关键问题，一是要记住哪 些可能的路线已经试探过，二是在回溯到前一步时 要消除当前步的影响。 使用一个数据结构记住试探的路

5、线，到最后一步时 试探的路线就是问题的解。使用整数数组存放每一 行的皇后在哪一列，为确定某一步是否合法，可用 二维数组模拟棋盘，当某行某列放有皇后时设置对 应元素的值为USE，否则设置为EMPTY。 使用类ChessBd模拟棋盘，提供成员函数实现初始 化棋盘、检查某位置是否能放置皇后、放置皇后到 某行某列以及清除某位置的皇后等功能。类Queen 用于获取所有的解。 8页 共40页 目录退出目录 三、案例设计 9页 共40页 目录退出目录 枚举类型STATUS 枚举类型BOOLEAN 10页 共40页 目录退出目录 （3）ChessBd类的设计 ChessBd类的设计如图所示。 ChessBd类

6、图 11页 共40页 目录退出目录 12页 共40页 目录退出目录 13页 共40页 目录退出目录 14页 共40页 目录退出目录 （4）Queen类的设计 Queen类的设计如图所示。 Queen类图 15页 共40页 目录退出目录 16页 共40页 目录退出目录 17页 共40页 目录退出目录 2主程序设计 在主函数中声明了一个Queen类的对象 queen，随后的所有操作都是调用Queen类 和ChessBd类的成员函数来完成的。其中， Queen类中的私有数据成员board又是 ChessBd类的对象。首先找出问题的第一个 解，找到则显示，然后继续寻找其他解， 每找到一套解则画图显示，

7、直到无解可找 ，则结束程序。程序流程图如图所示。 18页 共40页 目录退出目录 主程序调用流程图 19页 共40页 目录退出目录 四、案例实现 20页 共40页 目录退出目录 21页 共40页 目录退出目录 22页 共40页 目录退出目录 23页 共40页 目录退出目录 24页 共40页 目录退出目录 25页 共40页 目录退出目录 26页 共40页 目录退出目录 27页 共40页 目录退出目录 28页 共40页 目录退出目录 29页 共40页 目录退出目录 30页 共40页 目录退出目录 31页 共40页 目录退出目录 32页 共40页 目录退出目录 33页 共40页 目录退出目录 34页

8、 共40页 目录退出目录 35页 共40页 目录退出目录 36页 共40页 目录退出目录 37页 共40页 目录退出目录 38页 共40页 目录退出目录 五、案例总结与提高 案例总结 本案例主要是运用OOP的思想结合回溯 算法来求解问题。这个案例的需求和要 实现的任务简单明了，但程序相对来说 较难理解。读者需要对这个算法进行深 入的剖析，注意将问题分步骤来求解。 即：先利用回溯算法找出第一个解，再 在前一个解的基础上利用回溯算法找出 下一个解。 39页 共40页 目录退出目录 案例提高 在全面理解的基础上，读者可以对本 案例加以改动与提高： 目前本案例的所有可能的解未永久 保存，读者可以将所有的解保存在 文件中作为阅读理解程序时的参考 。 读者可考虑修改棋盘和皇后的显示 格式，使得显示效果更加美观。 40页 共40页