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

1、2021/3/91八皇后問(wèn)題八皇后問(wèn)題2021/3/92n1八皇后問(wèn)題背景八皇后問(wèn)題背景n2盲目的枚舉算法盲目的枚舉算法n3加約束的枚舉算法加約束的枚舉算法n4回溯法及基本思想回溯法及基本思想n5 回溯法應(yīng)用回溯法應(yīng)用n6八皇后問(wèn)題的遞歸回溯算法八皇后問(wèn)題的遞歸回溯算法n7八皇后問(wèn)題的非遞歸回溯算法八皇后問(wèn)題的非遞歸回溯算法 2021/3/93【背景背景】 八皇后問(wèn)題是一個(gè)以國(guó)際象棋為背八皇后問(wèn)題是一個(gè)以國(guó)際象棋為背景的問(wèn)題：景的問(wèn)題： 如何能夠在如何能夠在 88 的國(guó)際象棋棋盤(pán)上的國(guó)際象棋棋盤(pán)上放置八個(gè)皇后，使得任何一個(gè)皇后都放置八個(gè)皇后，使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后？為了達(dá)到無(wú)

2、法直接吃掉其他的皇后？為了達(dá)到此目的，任兩個(gè)皇后都不能處于同一此目的，任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上。條橫行、縱行或斜線上。2021/3/94八皇后問(wèn)題八皇后問(wèn)題q要在要在8*8的國(guó)際象棋棋盤(pán)中放的國(guó)際象棋棋盤(pán)中放8個(gè)皇后，使任意兩個(gè)皇個(gè)皇后，使任意兩個(gè)皇后都不能互相吃掉。后都不能互相吃掉。規(guī)則：皇后能吃掉同一行、同一規(guī)則：皇后能吃掉同一行、同一列、同一對(duì)角線的任意棋子。求所有的解。列、同一對(duì)角線的任意棋子。求所有的解。q八皇后的兩組解八皇后的兩組解2021/3/95【問(wèn)題分析問(wèn)題分析】n設(shè)八個(gè)皇后為設(shè)八個(gè)皇后為xi，分別在第，分別在第i行行(i=1，2，3，4，8)；n問(wèn)題的解

3、狀態(tài)問(wèn)題的解狀態(tài)：可以用：可以用(1,x1)，(2,x2)，(8,x8)表示表示8個(gè)個(gè)皇后的位置；皇后的位置；q由于行號(hào)固定，可簡(jiǎn)單記為：由于行號(hào)固定，可簡(jiǎn)單記為：(x1,x2,x3,x4,x5,x6,x7,x8)；n問(wèn)題的解空間問(wèn)題的解空間：(x1,x2,x3,x4,x5,x6,x7,x8)，1xi8(i=1，2，3，4，8)，共，共88個(gè)狀態(tài)；個(gè)狀態(tài)；n約束條件約束條件：八個(gè)：八個(gè)(1,x1),(2,x2) ,(3,x3),(4,x4) ,(5,x5), (6,x6) , (7,x7), (8,x8)不在同一行、同一列和同一對(duì)角線上。不在同一行、同一列和同一對(duì)角線上。n原問(wèn)題即：在解空間中

4、原問(wèn)題即：在解空間中尋找符合約束條件尋找符合約束條件的解狀態(tài)。的解狀態(tài)。n按什么順序去搜？按什么順序去搜？q目標(biāo)是沒(méi)有漏網(wǎng)之魚(yú)，盡量速度快。目標(biāo)是沒(méi)有漏網(wǎng)之魚(yú)，盡量速度快。2021/3/96枚舉得有個(gè)順序，否則枚舉得有個(gè)順序，否則輕則有漏的、重復(fù)的；輕則有漏的、重復(fù)的；重則無(wú)法循環(huán)表示。重則無(wú)法循環(huán)表示。2 【問(wèn)題設(shè)計(jì)問(wèn)題設(shè)計(jì)】盲目的枚舉算法盲目的枚舉算法na 盲目的枚舉算法盲目的枚舉算法q通過(guò)通過(guò)8重循環(huán)模擬搜索空間中的重循環(huán)模擬搜索空間中的88個(gè)狀態(tài)；個(gè)狀態(tài)；q按按枚舉思想枚舉思想，以以DFS的方式的方式，從第，從第1個(gè)皇后在第個(gè)皇后在第1列開(kāi)始列開(kāi)始搜索，枚舉出所有的搜索，枚舉出所有的“

5、解狀態(tài)解狀態(tài)”：n從中找出滿足約束條件的從中找出滿足約束條件的“答案狀態(tài)答案狀態(tài)”。n約束條件？約束條件？2021/3/971.按什么順序去查找所有的解按什么順序去查找所有的解 a.盲目的枚舉算法盲目的枚舉算法 void main() int x100; for (x1=1;x1=10;x1+) for (x2=1;x2=10;x2+) for (x3=1;x3=10;x3+) for (x4=1;x4=10;x4+) for (x5=1;x5=10;x5+) for (x6=1;x6=10;x6+) for (x7=1;x7=10;x7+) for (x8=1;x8=10;x8+) if (

6、check(x)=0) printf(x); 2021/3/98該如何解決沖突的問(wèn)題呢？該如何解決沖突的問(wèn)題呢？1.行；我們是按照行枚舉的，保證了一行一個(gè)皇后；行；我們是按照行枚舉的，保證了一行一個(gè)皇后；2.列：判斷是否存在列：判斷是否存在xi=xj3.對(duì)角線：主對(duì)角線的對(duì)角線：主對(duì)角線的i-j與從對(duì)角線的與從對(duì)角線的i+j存在特殊關(guān)系，如存在特殊關(guān)系，如圖：圖：2021/3/99盲目的枚舉算法盲目的枚舉算法n約束條件？約束條件？q不在同一列：不在同一列：xixj；q不在同一主對(duì)角線上：不在同一主對(duì)角線上：xi-i xj-j；q不在同一負(fù)對(duì)角線上：不在同一負(fù)對(duì)角線上：xi+i xj+j。q違規(guī)

7、的情況可以整合改寫(xiě)為：違規(guī)的情況可以整合改寫(xiě)為：nabs(xi - xj)=abs( i-j ) or (xi = xj)2021/3/910盲目的枚舉算法盲目的枚舉算法queen1( ) int a9; for (a1=1;a1=8;a1+) for (a2=1;a2=8;a2+) for (a3=1;a3=8;a3+) for (a4=1;a4=8;a4+) for (a5=1;a5=8;a5+) for (a6=1;a6=8;a6+) for(a7=1;a7=8;a7+) for(a8=1;a8=8;a8+)if (check(a,8)=0) continue; else for(i=1

8、;i=8;i+) print(ai); check1(a,n)int i,j; for(i=2;i=n;i+) for(j=1;j=i-1;j+) if (ai=aj) or (abs(ai-aj)=abs(i-j) return(0); return(1); 雙重循環(huán)，任意兩個(gè)皇雙重循環(huán)，任意兩個(gè)皇后之間都必須檢查。后之間都必須檢查。用用a1a8存儲(chǔ)存儲(chǔ)x1x82021/3/911n有有“通用的解題法通用的解題法”之稱。之稱。n回溯法的基本做法是回溯法的基本做法是搜索搜索，或是一種組織得井井有條，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適的，能避免不必要搜索的窮舉式

9、搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題。用于解一些組合數(shù)相當(dāng)大的問(wèn)題。n回溯法在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根回溯法在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索。先策略搜索。1 回溯法回溯法回溯法指導(dǎo)思想回溯法

10、指導(dǎo)思想走不通，就掉頭。走不通，就掉頭。 2021/3/912n求問(wèn)題所有解：要回溯到根，且根結(jié)點(diǎn)的所有子樹(shù)都求問(wèn)題所有解：要回溯到根，且根結(jié)點(diǎn)的所有子樹(shù)都已被搜索遍才結(jié)束。已被搜索遍才結(jié)束。n求任一解：只要搜索到問(wèn)題的一個(gè)解就可結(jié)束。求任一解：只要搜索到問(wèn)題的一個(gè)解就可結(jié)束。1 回溯法回溯法2021/3/9131 回溯算法設(shè)計(jì)過(guò)程回溯算法設(shè)計(jì)過(guò)程nstep1 確定問(wèn)題的解空間；確定問(wèn)題的解空間；nstep2 確定結(jié)點(diǎn)的擴(kuò)展規(guī)則；確定結(jié)點(diǎn)的擴(kuò)展規(guī)則；nstep3 搜索解空間。搜索解空間。2021/3/9142 回溯法應(yīng)用回溯法應(yīng)用-加約束的枚舉算法加約束的枚舉算法n如果能夠排除那些沒(méi)有前途的狀

11、態(tài)，會(huì)節(jié)約時(shí)間；如果能夠排除那些沒(méi)有前途的狀態(tài)，會(huì)節(jié)約時(shí)間；n如何提前發(fā)現(xiàn)？如何提前發(fā)現(xiàn)？回溯法指導(dǎo)思想回溯法指導(dǎo)思想走不通，就掉頭走不通，就掉頭 q如如(1,1, x3,x4,x5,x6,x7,x8)沒(méi)有必要再擴(kuò)展；沒(méi)有必要再擴(kuò)展；n這種狀態(tài)擴(kuò)展后會(huì)產(chǎn)生這種狀態(tài)擴(kuò)展后會(huì)產(chǎn)生86個(gè)結(jié)點(diǎn)；個(gè)結(jié)點(diǎn)；q同樣的同樣的(1,2, x3,x4,x5,x6,x7,x8)，也應(yīng)被排除。也應(yīng)被排除。q在每一次擴(kuò)展在每一次擴(kuò)展E結(jié)點(diǎn)后，都進(jìn)行檢查；結(jié)點(diǎn)后，都進(jìn)行檢查；n對(duì)檢查結(jié)果如何處理？對(duì)檢查結(jié)果如何處理？q檢查合格的才繼續(xù)向下擴(kuò)展；檢查合格的才繼續(xù)向下擴(kuò)展；q遇到不合格的遇到不合格的“掉頭就走掉頭就走”。20

12、21/3/915n只要當(dāng)前枚舉到的狀態(tài)可行，就繼續(xù)枚舉下去。只要當(dāng)前枚舉到的狀態(tài)可行，就繼續(xù)枚舉下去。當(dāng)找到一種方案或者無(wú)法繼續(xù)枚舉下去時(shí)，就退當(dāng)找到一種方案或者無(wú)法繼續(xù)枚舉下去時(shí)，就退回到上一狀態(tài)。退回到上一狀態(tài)的過(guò)程叫做回溯，回到上一狀態(tài)。退回到上一狀態(tài)的過(guò)程叫做回溯，枚舉下一個(gè)狀態(tài)的過(guò)程叫做遞歸。枚舉下一個(gè)狀態(tài)的過(guò)程叫做遞歸。n回溯就是像人走迷宮一樣，先選擇一個(gè)前進(jìn)方向回溯就是像人走迷宮一樣，先選擇一個(gè)前進(jìn)方向嘗試，一步步試探，在遇到死胡同不能再往前的嘗試，一步步試探，在遇到死胡同不能再往前的時(shí)候就會(huì)退到上一個(gè)分支點(diǎn)，另選一個(gè)方向嘗試，時(shí)候就會(huì)退到上一個(gè)分支點(diǎn)，另選一個(gè)方向嘗試，而在前進(jìn)

13、和回撤的路上都設(shè)置一些標(biāo)記，以便能而在前進(jìn)和回撤的路上都設(shè)置一些標(biāo)記，以便能夠正確返回，直到達(dá)到目標(biāo)或者所有的可行方案夠正確返回，直到達(dá)到目標(biāo)或者所有的可行方案都已經(jīng)嘗試完為止。都已經(jīng)嘗試完為止。2021/3/9162 回溯法應(yīng)用回溯法應(yīng)用-例例1 b加約束的枚舉算法加約束的枚舉算法2021/3/917我們可以依次確定每一行皇后我們可以依次確定每一行皇后的位置的位置如果在某一列可以放下一個(gè)皇如果在某一列可以放下一個(gè)皇后，我們就在這里放下，并搜后，我們就在這里放下，并搜索下一行索下一行若無(wú)法放下皇后則回到上一行，若無(wú)法放下皇后則回到上一行，即回溯即回溯當(dāng)當(dāng)n行的皇后都已確定后，我們行的皇后都已確

14、定后，我們就找到了一種方案就找到了一種方案2021/3/9182 例例1 b加約束的枚舉算法加約束的枚舉算法queen1( )int a9; for (a1=1;a1=8;a1+) for (a2=1;a2=8;a2+) if ( check(a,2)=0 ) continue; for (a3=1;a3=8;a3+) if (check(a,7)=0) continue; for(a8=1;a8=8;a8+) if (check(a,8)=0)continue; else for(i=1;i=8;i+) print(ai); n此算法可讀性很好，此算法可讀性很好，體現(xiàn)了體現(xiàn)了“回溯回溯”。但。但它只能解決八皇后問(wèn)它只能解決八皇后問(wèn)題，而不能解決任意題，而不能解決任意的的n皇后問(wèn)題。皇后問(wèn)題。check2 (int a ,int n)/多次被調(diào)用，只是一重循環(huán)多次被調(diào)用，只是一重循環(huán) int i; for(i=1;in) 即表示最后一個(gè)皇后擺放完畢，輸出結(jié)果即表示最后一個(gè)皇后擺放完畢，輸出結(jié)果; else for(i=下界下界 ; i0(有路可走有路可走) and (未達(dá)到目標(biāo)未達(dá)到目標(biāo)) /還未回溯到頭還未回溯到頭 if (i=n) 搜索到一個(gè)解，輸出搜索到一個(gè)解，輸出; /搜索到葉結(jié)點(diǎn)搜索到葉結(jié)點(diǎn) else