八皇后问题及其扩展解法.doc

《八皇后问题及其扩展解法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C++实现八皇后问题及其扩展N皇后问题(经典回溯算法)八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用八皇后问题是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一

2、行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。事实上就是有92种解法。了解了基本的原理后,我们开始分析:1.我们需要一个数据存放已经放置皇后的位置,用指针表示的一维数据*position,长度为N(N为放置的皇后总数),可能有人会问为什么不用二维数组,用下票i,j准备定位,事实是这样的,因为该问题是每行,每列,每组对角线只可能出现一个皇后,所以用一维数据position+i中的i则能代码第几行,而值*(position+i)则表示该行中的列值

3、,其实质与二维数组无异.2.判断每行可放置皇后,假设要判断第n行,则从position中从0到n-1每一个已放皇后的位置判断(列,对角线)具体算法如下:#include#include#includeusingnamespacestd;int*position;//放置的位置intqueen;//皇后数目intcount;//第N种可能性//判断第n行是否放置皇后boolSignPoint(intn){for(inti=0;i

4、+n))//该列已经放置过皇后了returnfalse;if(abs(*(position+i)-*(position+n))==n-i)//对角线已经放置过了returnfalse;}returntrue;}//设置皇后voidSetQueen(intn=0){if(queen==n){//该处可以改成自己想要的显示方式printf("NO.%d:",++count);printf("");for(inti=0;i

5、}else{printf("0");}}printf("");}printf("");return;}else{for(inti=0;i>queen;position=(int*)malloc(sizeof(int));SetQueen();cout<<"摆放完毕"<

6、ndl;cin.get();cin.get();return0;}