C++课件案例十八八皇后问题

C++课件案例十八八皇后问题null案例十八八皇后问题案例十八八皇后问题本案例知识要点数组的使用回溯算法的使用类的设计和使用一、案例需求一、案例需求案例描述八皇后问题是1850年由数学家高斯提出来的，该问题在88的国际象棋棋盘上放置8个皇后，条件是做到没有一个皇后能“吃掉”任何其他皇后，即没有任何两个皇后被放置在棋盘的同一行、同一列或同一对角线上。本案例利用回溯算法穷举出该问题的所有解。案例效果图本案例效果如图所示。八皇后问题案例效果图八皇后问题案例效果图null功能说明利用回溯算法穷举出八皇后问题的所有...

null 案例十八八皇后问题案例十八八皇后问题本案例知识要点数组的使用回溯算法的使用类的设计和使用一、案例需求一、案例需求案例描述八皇后问题是1850年由数学家高斯提出来的，该问题在88的国际象棋棋盘上放置8个皇后，条件是做到没有一个皇后能“吃掉”任何其他皇后，即没有任何两个皇后被放置在棋盘的同一行、同一列或同一对角线上。本案例利用回溯算法穷举出该问题的所有解。案例效果图本案例效果如图所示。八皇后问题案例效果图八皇后问题案例效果图null功能说明利用回溯算法穷举出八皇后问题的所有的解。程序结束后，采用图形化方式顺序输出所有的可能的解，即对于每一个解都要画出一个“棋盘”，其中“Q”代表皇后的位置。二、案例分析二、案例分析八皇后问题具有这样的性质：解决问题要分若干步，每步有几种可能的求解路线，当一种可能路线求解不成功时，需要回头再试另一种，直到最后某条路线达到目标而解决整个问题。如果各种路线都不成功，则说明问题不存在解。可以使用回溯算法的基本思想来解决此问题。先将棋盘初始化，刚开始将8个皇后都放在棋盘的外列，即第9列，并照此对结果数组进行初始化。然后从头开始一行一行地解决问题，从每一行的第一列开始扫描。如果在第I行找到了合适位置，则存储到solution[I-1]中，然后看下一行，即第I+1行，如果在第I+1行找到了合适位置，则存入数组solution[I]中，如果第I+1行没有合适的位置，那就说明上一行（第I行）皇后的位置不当。此时，就应该重新调整上一行（第I行）皇后的位置，然后再判断第I行的后续列有没有合适的位置，这就是回溯的含义。如果按照这个顺序成功地安排好了全部的行，就说明得到了一套完整的解。null有了一个完整的解后，如果保留前七行的皇后位置不动，考虑将最后一行的皇后挪动到其他位置，看看是否也是合适的解，如果可以，显然这就是另外一套解。该套解和前面的解的区别就是只有最后一行不同。也就是说，保持棋盘的初始值为“前一套解”，从最后一行开始向后面的列挪动“皇后”，试探其他的解，如果最后一行没有合适的位置，就上推一行。据此思路，直到从后向前回溯到第一行，则所有的解就都找到了。找第一套解与找其他的解，回溯的算法和思想基本相似。区别在于，找第一套解时，棋盘初始状态是皇后在棋盘外面，在第9列，从第一行开始从上到下扫描。而找其他解的时候，棋盘的初始状态是其他的解，从最后一行开始由下到上开始扫描。nullnull使用回溯算法要解决两个关键问题，一是要记住哪些可能的路线已经试探过，二是在回溯到前一步时要消除当前步的影响。使用一个数据结构记住试探的路线，到最后一步时试探的路线就是问题的解。使用整数数组存放每一行的皇后在哪一列，为确定某一步是否合法，可用二维数组模拟棋盘，当某行某列放有皇后时设置对应元素的值为USE，否则设置为EMPTY。使用类ChessBd模拟棋盘，提供成员函数实现初始化棋盘、检查某位置是否能放置皇后、放置皇后到某行某列以及清除某位置的皇后等功能。类Queen用于获取所有的解。三、案例设计三、案例设计null枚举类型STATUS 枚举类型BOOLEAN null （3）ChessBd类的设计 ChessBd类的设计如图所示。ChessBd类图 nullnullnullnull （4）Queen类的设计 Queen类的设计如图所示。Queen类图 nullnullnull2．主程序设计在主函数中声明了一个Queen类的对象queen，随后的所有操作都是调用Queen类和ChessBd类的成员函数来完成的。其中，Queen类中的私有数据成员board又是ChessBd类的对象。首先找出问题的第一个解，找到则显示，然后继续寻找其他解，每找到一套解则画图显示，直到无解可找，则结束程序。程序流程图如图所示。主程序调用流程图主程序调用流程图四、案例实现四、案例实现nullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnullnull五、案例总结与提高五、案例总结与提高案例总结本案例主要是运用OOP的思想结合回溯算法来求解问题。这个案例的需求和要实现的任务简单明了，但程序相对来说较难理解。读者需要对这个算法进行深入的剖析，注意将问题分步骤来求解。即：先利用回溯算法找出第一个解，再在前一个解的基础上利用回溯算法找出下一个解。null案例提高在全面理解的基础上，读者可以对本案例加以改动与提高：目前本案例的所有可能的解未永久保存，读者可以将所有的解保存在文件中作为阅读理解程序时的参考。读者可考虑修改棋盘和皇后的显示格式，使得显示效果更加美观。

                    本文档为【C++课件 案例十八  八皇后问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

C++课件 案例十八 八皇后问题

你可能还喜欢

C++课件案例十八八皇后问题