文档介绍：算法大作业
电子工程学院
在n×n格的棋盘上放置彼此不受攻击的n个皇后,按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子,求解可以放置的方法种数。
n后问题等于于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。即规定每一列放一个皇后,不会造成列上的冲突;当第i行被某个皇后占领后,则同一行上的所有空格都不能再放皇后,要把以i为下标的标记置为被占领状态。
解决冲突问题:
这个问题包括了行,列,两条对角线;
列:规定每一列放一个皇后,不会造成列上的冲突;
行:当第i行被某个皇后占领后,则同一行上的所有空格都不能再放皇后,要把以i为下标的标记置为被占领状态;
对角线:对角线有两个方向。在这我把这两条对角线称为:主对角线和从对角线。在同一对角线上的所有点(设下标为(i,j)),要么(i+j)是常数,要么(i-j)是常数。因此,当第i个皇后占领了第j列后,要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。
算法设计
因为n皇后问题,从n大于11开始求解过程耗时就很长,所以定义x数组的最大值MAXNUM=30;即最大可解决30皇后问题。
判断当前位置是否可放置皇后
皇后k在第k行第x[k]列时,x[i]==x[k] 时,两皇后在同一列上;abs(x[i]-x[k])==abs(i-k)时,两皇后在同一斜线上;两种情况两皇后都可相互攻击,返回false表示不符合条件。
bool Place(int k)
{
int i;
i=1;
while(i<k)
{
if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))
return false;
i=i+1;
}
return true;
输出当前解
void Print(int x[],int n)
{
num++;
printf("第%d\t种解法:(",num);
for(int i=1;i<=n;i++)
{
printf("%d,",x[i]);
if(i%n==0)printf(");\n");
}
回溯法搜索解空间
void NQueens(int n)
{
int k=1;
x[1]=0;
while(k>0)
{
x[k]+=1;
while(x[k]<=n&&!Place(k))
x[k]+=1;
if(x[k]<=n)
{
if(k==n)
Print(x,n);
else
{
k=k+1;
x[k]=0;
}
}
//回溯至上一行;
else
k--;
}
}
实验结果及分析
n皇后问题解的情况
皇后的个数
问题的解
N=1
X=(1)
N=2
无解
N=3
无解
N=4
X1=(2,4,1,3); X2=(3,1,4,2)
N=5
X1=(1,3,5,2,4); X2=(1,4,2,5,3); X3=(2,4,1,3,5); X4=(2,5,3,1,4);
X5=(3,1,4,2,5); X6=(3,5,2,4,1); X7=(4,1,3