文档介绍：皇后控制问题
吴钦阳
2007-7
解题报告
1
皇后控制问题
问题描述
在一个n×n个方格组成的棋盘上的任一方格中放置一个皇后，该皇后可以控制他所在的行，列以及对角线上的所有方格。
对于给定的自然数n，在n×n个方格组成的 y是用来记录每行皇后可行位置
a是用来记录最优解皇后位置
z是用来记录皇后控制的方格
int cmin,c;//cmin记录最优皇后个数，c为当前个数
RandomNumber rnd;//随机数产生器定义在类里,随机 效果更好，后面有解释
};
7
程序实现——函数说明
类Queen的私有成员函数Place(k)用于测试皇后k置于第x[k]列的合法性
bool Queen::Place(int k)
{//测试皇后k置于第x[k]列的合法性,x[k]和x[j]都大于0时候比较
if(x[k]>0)
for(int j=1;j<k;j++)
if((x[j]>0)&&((abs(k-j)==abs(x[j]-x[k]))||x[j]==x[k]))
return false;
return true;
}
对角线上的冲突
列上的冲突
8
程序实现——函数说明
类Queen的私有成员函数ctrl(m)
用于测试皇后是否已控制棋盘m*m
bool Queen::ctrl(int m)
{int i,j,u,v,count=0;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++) z[i][j]=0;//初始置0
for(i=1;i<=m;i++)
{ if(x[i]>0) // i行有皇后时
{ for(j=1;j<=m;j++) {z[i][j]=1;z[j][x[i]]=1;} // i行,x[i]列所有元素都控制
for(u=i,v=x[i];u>=1&&v>=1;u--,v--) z[u][v]=1;//(i,x[i])左上对角线所有元
素都控制
for(u=i,v=x[i];u<=m&&v>=1;u++,v--) z[u][v]=1;//(i,x[i])左下对角线
for(u=i,v=x[i];u>=1&&v<=m;u--,v++) z[u][v]=1;//(i,x[i])右上对角线
for(u=i,v=x[i];u<=m&&v<=m;u++,v++) z[u][v]=1;//(i,x[i])右下对角线
} }
for(i=1;i<=m;i++)
for(j=1;j<=m;j++) count+=z[i][j];//统计皇后控制的方格数
return(count==m*m);}
O
O
O
O
O
9
程序实现——函数说明
类Queen的私有成员函数QueensLV(stopVegas)实现在棋盘上随机放置若干个皇后的拉斯维加斯算法，其中stopVegas表示用该算法计算皇后的行数。
int Queen::QueensLV(int stopVegas)
{//RandomNumber rnd;//随机数产生器定义在类里,随机效果更好，后面有解释
int k=1;
int count;
c=0;
while(k<=stopVegas)
{ count=0;
y[count++]=0;//不放可行,即0都是可行的, y是记录每行皇后可行位置
for(int i=1;i<=n;i++)
{ x[k]=i;
if(Place(k)) y[count++]=i;
}
if((x[k++]=y[(count)])>0) c++;//可以为0,并统计皇后个数
}
return c;//返回己放置的皇后个数
}
随机位置，可以不放
10