八皇后问题是一个古老而著名的问题

《八皇后问题是一个古老而著名的问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、八皇后问题是一个古老而著名的问题，它是回溯算法的典型例题。该问题是十九世纪德国著名数学家高斯于1850年提出的：在8行8列的国际象棋棋盘上摆放着八个皇后。若两个皇后位于同一行、同一列或同一对角线上，则称为它们为互相攻击。在国际象棋中皇后是最强大的棋子，因为它的攻击范围最大，图6-15显示了一个皇后的攻击范围。 图6-15皇后的攻击范围现在要求使这八个皇后不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。现代教学中，把八皇后问题当成一个经典递

2、归算法例题。图6-16显示了两种八个皇后不相互攻击的情况。图6-16八个皇后不相互攻击的情况现在来看如何使用回溯法解决八皇后问题。这个算法将在棋盘上一列一列地摆放皇后直到八个皇后在不相互攻击的情况下都被摆放在棋盘上，算法便终止。当一个新加入的皇后因为与已经存在的皇后之间相互攻击而不能被摆在棋盘上时，算法便发生回溯。一旦发生这种情况，就试图把最后放在棋盘上的皇后移动到其他地方。这样做是为了让新加入的皇后能够在不与其它皇后相互攻击的情况下被摆放在棋盘的适当位置上。例如图6-17所示的情况，尽管第7个皇后不会与已经放在棋盘上的任何一皇后放生攻击，但仍然需要将它移除并发生回溯，因为无法为第8个皇后

3、在棋盘上找到合适的位置。图6-17需要发生回溯的情况算法的回溯部分将尝试移动第7个皇后到第7列的另外一点来为第8个皇后在第8列寻找一个合适的位置。如果第7个皇后由于在第7列找不到合适的位置而无法被移动，那么算法就必须去掉它然后回溯到第6列的皇后。最终算法不断重复着摆放皇后和回溯的过程直到找到问题的解为止。下面给出了求解八皇后问题的示例程序。#include#includeusingnamespacestd;//首先要求皇后不冲突，那么每行只应该有一个皇后//用queens[]数组在存储每个皇后的位置//例如:queens[m]=n表示第m行的皇后放在第

4、n列上#defineMAX8intsum=0;classQueenPuzzle{ intqueens[MAX];//存储每行皇后的列标 public: voidprintOut();//打印结果 intIsValid(intn);//判断第n个皇后放上去之后，是否合法 voidplaceQueen(inti);//递归算法放置皇后};voidQueenPuzzle::printOut(){ for(inti=0;i

5、";  }  cout<

6、位置  if(IsValid(i))   placeQueen(i+1); }}//判断第n个皇后放上去之后，是否合法，即是否无冲突 intQueenPuzzle::IsValid(intn) {  //将第n个皇后的位置依次于前面n－1个皇后的位置比较。  for(inti=0;i

7、rn1; }voidmain(){ QueenPuzzlequeen; queen.placeQueen(0); cout<<"共"<