算法设计及实验分析五：八皇后问题

《算法设计及实验分析五：八皇后问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与实验分析无五：八皇后问题班级：网络1101姓名：齐岳川学号：1111610210日期：2013.5.21一：实验名称：八皇后问题二：实验内容：在8×8格的国际象棋上摆放八皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。虽然问题的关键在于如何判定某个皇后所在的行、列、斜线是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在“/”斜线上的行列值之和相同；如果在对角线上，则行列号之和或之差相等，逐个纪录符合题意的情况

2、,最终得出解。回溯法：回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。三：程序清单：#include#include#include#include1staticcharQueen[8][8];staticinta[8];staticintb[15

3、];staticintc[15];staticintiQueenNum=0;staticintiNum=1;voidiQueen(inti);voidmeasure1(){intiLine;intiColumn;for(iLine=0;iLine<8;iLine++){a[iLine]=0;for(iColumn=0;iColumn<8;iColumn++)Queen[iLine][iColumn]='*';}for(iLine=0;iLine<15;iLine++)b[iLine]=c[iLine]=0;iQuee

4、n(0);};voidiQueen(inti){intiColumn;for(iColumn=0;iColumn<8;iColumn++){if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0){Queen[i][iColumn]='@';a[iColumn]=1;b[i-iColumn+7]=1;c[i+iColumn]=1;if(i<7)iQueen(i+1);else{intiLine;intiColumn;cout<<"(递归法)皇后摆放方式的第"<

5、m<<"种情况为："<

6、'<nul");iNum++;cout<