n皇后问题实验报告

-.z.N后问题算法一、实验目的及要求所要涉及或掌握的知识：1.

了解皇后相互攻击的条件：如果任意两个皇后在同一行，同一列或同一对角线，则她们相互攻击。2.

运用迭代的方法实现6皇后问题，求解得到皇后不相互攻击的一个解3.

在运用迭代的方法实现编程时，要注意回溯点二、问题描述及实验容对6皇后问题求解，用数组c[1…6]来存皇后的位置。c[i]=j表示第i个皇后放在第j列。最后程序运行的结果是c[1…6]={1,5,8,6,3,7}三、问题分析和算法描述6-QUEENS的算法表示：输入：空。输出：对应于6皇后问题的解的向量c[1…6]={1,5,8,6,3,7}1.

fork=1to62.

c[k]=0

//没有放皇后3.

endfor4.

flag=false5.

k=16.

whilek>=17.

whilec[k]<=58.

c[k]=c[k]+19.

ifc为合法着色

thensetflag=ture且从两个while循环退出10.

elseifc是部分解thenk=k+111.

endwhile12.

c[k]=0

//回溯并c[k]=013.

k=k-114.

endwhile15.

ifflag

thenoutputc16.

elseoutput“nosolution”四、具体实现*include<math.h>*include<time.h>*include<stdlib.h>*include<stdio.h>*include"iostream"usingnamespacestd;inttotal=0;//方案计数voidbacktrace(intqueen[],intN){inti,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(inti=0;i<N;i++)

{

for(intj=0;j<queen[i];j++)

cout<<"□";

cout<<"*";

for(intk=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;

}

elsequeen[i]++;//前一行皇后右移一列

}}}voidmain(){while(1){

clock_tstart,finish;

doubleduration;

intN;

cout<<"请输入皇后个数："<<endl;

cin>>N;

int*queen=newint[N];

for(inti=0;i<N;i++)queen[i]=0;//八皇后全放在第0列

intn=N;/*定义数组p[N]用来存放结果序列，n为行号*/

start=clock();

total=0;

backtrace(queen,N);

finish=clock();

duration=(double)(finish-start);

cout<<"为找出放置方法系统共耗时"<<duration/1000<<"秒！\n"<<endl;

delete[]queen;}}运行结果：回溯法求解八皇后问题2010-10-2918:28:56|

分类：

\o"算法分析"算法分析

|

标签：%d",queen[i]);

}

printf(")\n");

sum++;

}

intPLACE(intn)/*检查当前列能否放置皇后*/

{

inti;

for(i=0;i<n;i++)/*检查横排和对角线上是否可以放置皇后*/

{

if(queen[i]==queen[n]||abs(queen[i]-queen[n])==(n-i))

{

return1;

}

}

return0;

}

voidNQUEENS(intn)/*回溯尝试皇后位置,n为横坐标*/

{

inti;

for(i=0;i<ma*;i++)

{

queen[n]=i;/*将皇后摆到当前循环到的位置*/

if(!PLACE(n))

{

if(n==ma*-1)

{

show();/*如果全部摆好，则输出所有皇后的坐标*/

}

else

{

NQUEENS(n+1);/*