實(shí)驗(yàn)四 n皇后問題求解

《實(shí)驗(yàn)四 n皇后問題求解》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、實(shí)驗(yàn)四N皇后問題求解一、題目1）以Q-皇后問題為例，掌握回溯法的基本設(shè)計(jì)策略。2）掌握回溯法解決Q-皇后問題的算法并實(shí)現(xiàn)；二、算法設(shè)計(jì)思想回溯法是在包含問題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹。當(dāng)探索到某一結(jié)點(diǎn)時(shí)，要先判斷該結(jié)點(diǎn)是否包含問題的解，如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去，如果該結(jié)點(diǎn)不包含問題的解，則逐層向其祖先結(jié)點(diǎn)回溯。（其實(shí)回溯法就是對(duì)隱式圖的深度優(yōu)先搜索算法）。若用回溯法求問題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有可行的子樹都要已被搜索遍才結(jié)束。而若使用回溯法求任一個(gè)解時(shí)，只要搜索到問題的一個(gè)解就可以

2、結(jié)束。判斷解是否可行的條件：1.不在同一行或者同一列，x[i]!=x[j],i!=j2.不在一條斜線上，設(shè)兩個(gè)皇后在(i,j)和(k,l)位置，

3、i-k

4、!=

5、j-l

6、三、程序#include#includeintn,stack[100];//存當(dāng)前路徑inttotal;//路徑數(shù)intatt(int,int);voidmake(intl)//遞歸搜索以stack[l]為初結(jié)點(diǎn)的所有路徑{inti,j;//子結(jié)點(diǎn)個(gè)數(shù)if(l==n+1){total=total+1;//路徑數(shù)+1for(i=1;i<=n;i++)pr

7、intf("輸出皇后的列位置%-3d",stack[i]);//輸出第i行皇后的列位置stack[i]printf("");exit;//回溯}for(i=1;i<=n;i++){stack[l]=i;//算符i作用于生成stack[l-1]產(chǎn)生子狀態(tài)stack[l];if(!att(l,i))make(l+1);}//再無算符可用，回溯}intatt(intl,inti){intk;for(k=1;k

8、

9、i==stack[k])return1;return0;}intmain()

10、{printf("N=");scanf("%d",&n);total=0;//路徑數(shù)初始化為0make(1);//從結(jié)點(diǎn)1出發(fā)，遞歸搜索所有的路徑printf("%d",total);system("pause");return0;}四、運(yùn)行結(jié)果六、心得體會(huì)在解決N皇后的時(shí)候一開始有點(diǎn)不止如何著手，因?yàn)檫@里有個(gè)N的不確定性，所以選擇簡單少量的情況進(jìn)行具體考慮顯得相對(duì)容易了許多，還有一個(gè)值得注意的問題就是如何判斷要不要重新開始搜索，并且在已經(jīng)形成的簡單模型基礎(chǔ)上進(jìn)行改進(jìn)，使之也能滿足后面較復(fù)雜情況。