文档介绍：案例十八八皇后问题
本案例知识要点
数组的使用
回溯算法的使用
类的设计和使用
1页共40页
一、案例需求
案例描述
八皇后问题是1850年由数学家高斯提出来的,该问题在88的国际象棋棋盘上放置8个皇后,条件是做到没有一个皇后能“吃掉”任何其他皇后,即没有任何两个皇后被放置在棋盘的同一行、同一列或同一对角线上。
本案例利用回溯算法穷举出该问题的所有解。
案例效果图
本案例效果如图所示。
2页共40页
八皇后问题案例效果图
3页共40页
功能说明
利用回溯算法穷举出八皇后问题的所有的解。
程序结束后,采用图形化方式顺序输出所有的可能的解,即对于每一个解都要画出一个“棋盘”,其中“Q”代表皇后的位置。
4页共40页
二、案例分析
八皇后问题具有这样的性质:解决问题要分若干步,每步有几种可能的求解路线,当一种可能路线求解不成功时,需要回头再试另一种,直到最后某条路线达到目标而解决整个问题。如果各种路线都不成功,则说明问题不存在解。可以使用回溯算法的基本思想来解决此问题。
先将棋盘初始化,刚开始将8个皇后都放在棋盘的外列,即第9列,并照此对结果数组进行初始化。然后从头开始一行一行地解决问题,从每一行的第一列开始扫描。如果在第I行找到了合适位置,则存储到solution[I-1]中,然后看下一行,即第I+1行,如果在第I+1行找到了合适位置,则存入数组solution[I]中,如果第I+1行没有合适的位置,那就说明上一行(第I行)皇后的位置不当。此时,就应该重新调整上一行(第I行)皇后的位置,然后再判断第I行的后续列有没有合适的位置,这就是回溯的含义。如果按照这个顺序成功地安排好了全部的行,就说明得到了一套完整的解。
5页共40页
有了一个完整的解后,如果保留前七行的皇后位置不动,考虑将最后一行的皇后挪动到其他位置,看看是否也是合适的解,如果可以,显然这就是另外一套解。该套解和前面的解的区别就是只有最后一行不同。也就是说,保持棋盘的初始值为“前一套解”,从最后一行开始向后面的列挪动“皇后”,试探其他的解,如果最后一行没有合适的位置,就上推一行。据此思路,直到从后向前回溯到第一行,则所有的解就都找到了。
找第一套解与找其他的解,回溯的算法和思想基本相似。区别在于,找第一套解时,棋盘初始状态是皇后在棋盘外面,在第9列,从第一行开始从上到下扫描。而找其他解的时候,棋盘的初始状态是其他的解,从最后一行开始由下到上开始扫描。
6页共40页
7页共40页
使用回溯算法要解决两个关键问题,一是要记住哪些可能的路线已经试探过,二是在回溯到前一步时要消除当前步的影响。
使用一个数据结构记住试探的路线,到最后一步时试探的路线就是问题的解。使用整数数组存放每一行的皇后在哪一列,为确定某一步是否合法,可用二维数组模拟棋盘,当某行某列放有皇后时设置对应元素的值为USE,否则设置为EMPTY。
使用类ChessBd模拟棋盘,提供成员函数实现初始化棋盘、检查某位置是否能放置皇后、放置皇后到某行某列以及清除某位置的皇后等功能。类Queen用于获取所有的解。
8页共40页
三、案例设计
9页共40页
枚举类型STATUS
枚举类型BOOLEAN
10页共40页