n皇后問題實驗報告

-.z.N后問題算法一、實驗?zāi)康募耙笏婕盎蛘莆盏闹R：1.

了解皇后相互攻擊的條件：如果任意兩個皇后在同一行，同一列或同一對角線，則她們相互攻擊。2.

運用迭代的方法實現(xiàn)6皇后問題，求解得到皇后不相互攻擊的一個解3.

在運用迭代的方法實現(xiàn)編程時，要注意回溯點二、問題描述及實驗容對6皇后問題求解，用數(shù)組c[1…6]來存皇后的位置。c[i]=j表示第i個皇后放在第j列。最后程序運行的結(jié)果是c[1…6]={1,5,8,6,3,7}三、問題分析和算法描述6-QUEENS的算法表示：輸入：空。輸出：對應(yīng)于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循環(huán)退出10.

elseifc是部分解thenk=k+111.

endwhile12.

c[k]=0

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

k=k-114.

endwhile15.

ifflag

thenoutputc16.

elseoutput“nosolution”四、具體實現(xiàn)*include<math.h>*include<time.h>*include<stdlib.h>*include<stdio.h>*include"iostream"usingnamespacestd;inttotal=0;//方案計數(shù)voidbacktrace(intqueen[],intN){inti,j,k;cout<<"*為皇后放置位置\n";for(i=1;;){//首先安放第1行

if(queen[i]<N)

{//皇后還可調(diào)整

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++;//方案數(shù)加1

if(total%5==0)cout<<endl;

queen[N-1]++;//將第8個皇后右移一列，前8個不動

i=N-1;//此處是制造機會，如不成功則回溯，關(guān)鍵一步

}

else//當(dāng)前行皇后無法安置，回溯

{

queen[i]=0;//當(dāng)前行皇后回歸1列

i--;//回溯到前一行皇后

if(i<0)

{//回溯到數(shù)組1行之前，結(jié)束

cout<<"\n針對"<<N<<"皇后問題，"<<"一共找到"<<total<<"種放置方法。"<<endl;

cout<<endl;

return;

}

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

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

clock_tstart,finish;

doubleduration;

intN;

cout<<"請輸入皇后個數(shù)："<<endl;

cin>>N;

int*queen=newint[N];

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

intn=N;/*定義數(shù)組p[N]用來存放結(jié)果序列，n為行號*/

start=clock();

total=0;

backtrace(queen,N);

finish=clock();

duration=(double)(finish-start);

cout<<"為找出放置方法系統(tǒng)共耗時"<<duration/1000<<"秒！\n"<<endl;

delete[]queen;}}運行結(jié)果：回溯法求解八皇后問題2010-10-2918:28:56|

分類：

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

|

標(biāo)簽：%d",queen[i]);

}

printf(")\n");

sum++;

}

intPLACE(intn)/*檢查當(dāng)前列能否放置皇后*/

{

inti;

for(i=0;i<n;i++)/*檢查橫排和對角線上是否可以放置皇后*/

{

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

{

return1;

}

}

return0;

}

voidNQUEENS(intn)/*回溯嘗試皇后位置,n為橫坐標(biāo)*/

{

inti;

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

{

queen[n]=i;/*將皇后擺到當(dāng)前循環(huán)到的位置*/

if(!PLACE(n))

{

if(n==ma*-1)

{

show();/*如果全部擺好，則輸出所有皇后的坐標(biāo)*/

}

else

{

NQUEENS(n+1);/*