该程序是算法分析与设计里的n皇后处理程序,该程将n皇后图形化void backtrace(int queen[],int N)
{
int i, j, k;
cout<<"★为皇后放置位置\n";
for (i=1;;)
{ //首先安放第1行
if(queen[i]<N)
{ //皇后还可调整
k=0; //检查与第k个皇后是否互相攻击
while(k<i&&abs(queen[k]-queen[i])&&(abs(queen[k]-queen[i])-abs(k-i))) k++;
if (k<=i-1)
{ //与第k个皇后互相攻击
queen[i]++; //第i个皇后右移一列,重测
continue;
}
i++; //无冲突,安置下一行皇后
if(i<N) continue;
cout<<"第"<<total+1<<"种为:\n";
for(int i=0;i<N;i++)
{
for(int j=0;j<queen[i];j++)
cout<<"□";
cout<<"★";
for(int k=queen[i]+1;k<N;k++)
cout<<"□";
cout<<endl;
}
total++; //方案数加1
if(total%5==0) cout<<endl;
queen[N-1]++; // 将第8个皇后右移一列,前8个不动
i=N-1; //此处是制造机会,如不成功则回溯,关键一步
}
else //当前行皇后无法安置,回溯
{
queen[i]=0; //当前行皇后回归1列
i--; //回溯到前一行皇后
if(i<0)
{ //回溯到数组1行之前,结束
cout<<"\n针对 "<<N<<" 皇后问题,"<<"一共找到 "<<total<<" 种放置方法。 "<<endl;
cout<<endl;
return;
}
else queen[i]++; //前一行皇后右移一列
}
}
}