八皇后問(wèn)題詳細(xì)的解法課件

八皇后問(wèn)題1八皇后問(wèn)題詳細(xì)的解法1八皇后問(wèn)題背景2盲目的枚舉算法3加約束的枚舉算法4回溯法及基本思想5回溯法應(yīng)用6八皇后問(wèn)題的遞歸回溯算法7八皇后問(wèn)題的非遞歸回溯算法

2八皇后問(wèn)題詳細(xì)的解法【背景】

八皇后問(wèn)題是一個(gè)以國(guó)際象棋為背景的問(wèn)題：

如何能夠在8×8的國(guó)際象棋棋盤上放置八個(gè)皇后，使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后？為了達(dá)到此目的，任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上。3八皇后問(wèn)題詳細(xì)的解法八皇后問(wèn)題要在8*8的國(guó)際象棋棋盤中放8個(gè)皇后，使任意兩個(gè)皇后都不能互相吃掉。規(guī)則：皇后能吃掉同一行、同一列、同一對(duì)角線的任意棋子。求所有的解。八皇后的兩組解4八皇后問(wèn)題詳細(xì)的解法【問(wèn)題分析】設(shè)八個(gè)皇后為xi，分別在第i行(i=1，2，3，4……，8)；問(wèn)題的解狀態(tài)：可以用(1,x1)，(2,x2)，……，(8,x8)表示8個(gè)皇后的位置；由于行號(hào)固定，可簡(jiǎn)單記為：(x1,x2,x3,x4,x5,x6,x7,x8)；問(wèn)題的解空間：(x1,x2,x3,x4,x5,x6,x7,x8)，1≤xi≤8(i=1，2，3，4……，8)，共88個(gè)狀態(tài)；約束條件：八個(gè)(1,x1),(2,x2),(3,x3),(4,x4),(5,x5),(6,x6),(7,x7),(8,x8)不在同一行、同一列和同一對(duì)角線上。原問(wèn)題即：在解空間中尋找符合約束條件的解狀態(tài)。按什么順序去搜？目標(biāo)是沒(méi)有漏網(wǎng)之魚，盡量速度快。5八皇后問(wèn)題詳細(xì)的解法枚舉得有個(gè)順序，否則輕則有漏的、重復(fù)的；重則無(wú)法循環(huán)表示。2【問(wèn)題設(shè)計(jì)】盲目的枚舉算法a盲目的枚舉算法通過(guò)8重循環(huán)模擬搜索空間中的88個(gè)狀態(tài)；按枚舉思想，以DFS的方式，從第1個(gè)皇后在第1列開始搜索，枚舉出所有的“解狀態(tài)”：從中找出滿足約束條件的“答案狀態(tài)”。約束條件？6八皇后問(wèn)題詳細(xì)的解法1.按什么順序去查找所有的解

a.盲目的枚舉算法

voidmain()

{

intx[100];

for(x[1]=1;x[1]<=10;x[1]++)

for(x[2]=1;x[2]<=10;x[2]++)

for(x[3]=1;x[3]<=10;x[3]++)

for(x[4]=1;x[4]<=10;x[4]++)

for(x[5]=1;x[5]<=10;x[5]++)

for(x[6]=1;x[6]<=10;x[6]++)

for(x[7]=1;x[7]<=10;x[7]++)

for(x[8]=1;x[8]<=10;x[8]++)

if(check(x)==0)

{

printf(x);

}

}八皇后問(wèn)題詳細(xì)的解法該如何解決沖突的問(wèn)題呢？1.行；我們是按照行枚舉的，保證了一行一個(gè)皇后；2.列：判斷是否存在x[i]=x[j]3.對(duì)角線：主對(duì)角線的i-j與從對(duì)角線的i+j存在特殊關(guān)系，如圖：八皇后問(wèn)題詳細(xì)的解法盲目的枚舉算法約束條件？不在同一列：xi≠xj；不在同一主對(duì)角線上：xi-i≠xj-j；不在同一負(fù)對(duì)角線上：xi+i≠xj+j。違規(guī)的情況可以整合改寫為：abs(xi-xj)=abs(i-j))or(xi=xj)9八皇后問(wèn)題詳細(xì)的解法盲目的枚舉算法queen1(){inta[9];

for

(a[1]=1;a[1]<=8;a[1]++)

for

(a[2]=1;a[2]<=8;a[2]++)

for

(a[3]=1;a[3]<=8;a[3]++)

for

(a[4]=1;a[4]<=8;a[4]++) for

(a[5]=1;a[5]<=8;a[5]++) for

(a[6]=1;a[6]<=8;a[6]++)

for(a[7]=1;a[7]<=8;a[7]++) for(a[8]=1;a[8]<=8;a[8]++){

if(check(a,8)=0)continue;

else

for(i=1;i<=8;i++) print(a[i]); }}check1(a[],n){inti,j;

for(i=2;i<=n;i++)

for(j=1;j<=i-1;j++)

if(a[i]==a[j])or(abs(a[i]-a[j])==abs(i-j))

return(0);

return(1);

}雙重循環(huán)，任意兩個(gè)皇后之間都必須檢查。用a[1]~a[8]存儲(chǔ)x1~x810八皇后問(wèn)題詳細(xì)的解法有“通用的解題法”之稱?；厮莘ǖ幕咀龇ㄊ撬阉?，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題?；厮莘ㄔ趩?wèn)題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。1回溯法回溯法指導(dǎo)思想——走不通，就掉頭。11八皇后問(wèn)題詳細(xì)的解法求問(wèn)題所有解：要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。求任一解：只要搜索到問(wèn)題的一個(gè)解就可結(jié)束。1回溯法12八皇后問(wèn)題詳細(xì)的解法1回溯算法設(shè)計(jì)過(guò)程step1確定問(wèn)題的解空間；step2確定結(jié)點(diǎn)的擴(kuò)展規(guī)則；step3搜索解空間。13八皇后問(wèn)題詳細(xì)的解法2回溯法應(yīng)用-加約束的枚舉算法如果能夠排除那些沒(méi)有前途的狀態(tài)，會(huì)節(jié)約時(shí)間；如何提前發(fā)現(xiàn)？回溯法指導(dǎo)思想——走不通，就掉頭如(1,1,x3,x4,x5,x6,x7,x8)沒(méi)有必要再擴(kuò)展；這種狀態(tài)擴(kuò)展后會(huì)產(chǎn)生86個(gè)結(jié)點(diǎn)；同樣的(1,2,x3,x4,x5,x6,x7,x8)，…也應(yīng)被排除。在每一次擴(kuò)展E結(jié)點(diǎn)后，都進(jìn)行檢查；對(duì)檢查結(jié)果如何處理？檢查合格的才繼續(xù)向下擴(kuò)展；遇到不合格的“掉頭就走”。14八皇后問(wèn)題詳細(xì)的解法只要當(dāng)前枚舉到的狀態(tài)可行，就繼續(xù)枚舉下去。當(dāng)找到一種方案或者無(wú)法繼續(xù)枚舉下去時(shí)，就退回到上一狀態(tài)。退回到上一狀態(tài)的過(guò)程叫做回溯，枚舉下一個(gè)狀態(tài)的過(guò)程叫做遞歸?；厮菥褪窍袢俗呙詫m一樣，先選擇一個(gè)前進(jìn)方向嘗試，一步步試探，在遇到死胡同不能再往前的時(shí)候就會(huì)退到上一個(gè)分支點(diǎn)，另選一個(gè)方向嘗試，而在前進(jìn)和回撤的路上都設(shè)置一些標(biāo)記，以便能夠正確返回，直到達(dá)到目標(biāo)或者所有的可行方案都已經(jīng)嘗試完為止。八皇后問(wèn)題詳細(xì)的解法2回溯法應(yīng)用-例1b加約束的枚舉算法●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●………………●●●●●●●16八皇后問(wèn)題詳細(xì)的解法我們可以依次確定每一行皇后的位置如果在某一列可以放下一個(gè)皇后，我們就在這里放下，并搜索下一行若無(wú)法放下皇后則回到上一行，即回溯當(dāng)n行的皇后都已確定后，我們就找到了一種方案八皇后問(wèn)題詳細(xì)的解法2例1b加約束的枚舉算法queen1(){inta[9];

for

(a[1]=1;a[1]<=8;a[1]++)

for

(a[2]=1;a[2]<=8;a[2]++)

{if(check(a,2)==0)continue;

for

(a[3]=1;a[3]<=8;a[3]++)

…… {if(check(a,7)==0)continue;

for(a[8]=1;a[8]<=8;a[8]++){if(check(a,8)==0)continue;

else

for(i=1;i<=8;i++)print(a[i]);}}}}}}}}此算法可讀性很好，體現(xiàn)了“回溯”。但它只能解決八皇后問(wèn)題，而不能解決任意的n皇后問(wèn)題。check2(inta[],intn)

{//多次被調(diào)用，只是一重循環(huán)

inti;

for(i=1;i<=n-1;i++)

if(abs(a[i]-a[n])==abs(i-n))

or(a[i]==a[n])

return(0);

return(1);

}18八皇后問(wèn)題詳細(xì)的解法2回溯法應(yīng)用-算法說(shuō)明八皇后問(wèn)題中的核心代碼：遍歷過(guò)程函數(shù)；check函數(shù)。解決此類問(wèn)題的核心內(nèi)容：解空間樹的搜索算法；估值/判斷函數(shù)：判斷哪些狀態(tài)適合繼續(xù)擴(kuò)展，或者作為答案狀態(tài)。19八皇后問(wèn)題詳細(xì)的解法2回溯法應(yīng)用-n皇后問(wèn)題介紹過(guò)的方法：c遞歸回溯算法；d非遞歸回溯算法；策略：能進(jìn)則進(jìn)，不能進(jìn)則換，不能換則退。20八皇后問(wèn)題詳細(xì)的解法2回溯法應(yīng)用-算法框架-遞歸算法框架inta[n];Queens(intk){if(k>n)即表示最后一個(gè)皇后擺放完畢，輸出結(jié)果;

elsefor(i=下界;i<=上界;i++)//枚舉K個(gè)皇后所有可能的路徑

{依次從列頂端開始搜索，一直到列底端，直到找到合適位置,如果未找到，自動(dòng)返回上層遞歸a[k]=i;if(check(a,k))//滿足限界函數(shù)和約束條件，不沖突//遞歸擺放下一個(gè)皇后Queens(k+1);}}}21八皇后問(wèn)題詳細(xì)的解法22八皇后問(wèn)題詳細(xì)的解法2回溯法應(yīng)用-算法框架-非遞歸回溯框架inta[n],i;初始化數(shù)組a[]；i=1;While(i>0(有路可走))and(未達(dá)到目標(biāo))//還未回溯到頭

{if(i=n)搜索到一個(gè)解，輸出;//搜索到葉結(jié)點(diǎn)

else