算法设计与实验分析无五：八皇后问题
班级：网络1101姓名：齐岳川学号：1111610210日期：2013.5.21
一：实验名称：八皇后问题
二：实验内容：
在8×8格的国际象棋上摆放八皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。虽然问题的关键在于如何判定某个皇后所在的行、列、斜线是否有别的皇后；可以从矩阵的特点上找到规律，如果在同一行，则行号相同；如果在同一列上，则列号相同；如果同在“/”斜线上的行列值之和相同；如果在对角线上，则行列号之和或之差相等，逐个纪录符合题意的情况,最终得出解。
回溯法：
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
三：程序清单：
#include
#include
#include
#include
1
static char Queen[8][8];
static int a[8];
static int b[15];
static int c[15];
static int iQueenNum=0;
static int iNum=1;
void iQueen(int i);
void measure1()
{
int iLine;
int iColumn;
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;
iQueen(0);
};
void iQueen(int i)
{
int iColumn;
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
{
int iLine;
int iColumn;
cout<<"(递归法)皇后摆放方式的第"< for(iLine=0;iLine<8;iLine++) { for(iColumn=0;iColumn<8;iColumn++) cout< cout< } cout< for(iLine=0;iLine<8;iLine++) { for(iColumn=0;iColumn<8;iColumn++) { if(Queen[iLine][iColumn]=='@') cout<<"("< } } cout< system("pause>nul"); iNum++; cout< } Queen[i][iColumn]='*'; a[iColumn]=0; b[i-iColumn+7]=0; c[i+iColumn]=0; } } } 运行结果:
第二篇：实验五安全算法的设计
