算法設(shè)計(jì)與分析 課件 7.10-回溯法 - 典型應(yīng)用 - 兩種實(shí)現(xiàn) - n皇后問(wèn)題

算法設(shè)計(jì)與分析回溯法—n皇后問(wèn)題信息工程大學(xué)國(guó)家級(jí)實(shí)驗(yàn)教學(xué)示范中心計(jì)算機(jī)學(xué)科組規(guī)劃教材算法設(shè)計(jì)與分析Python案例詳解微課視頻版問(wèn)題描述：在n×n格的棋盤(pán)上放置彼此不受攻擊的n個(gè)皇后。按照國(guó)際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線(xiàn)上的棋子。n后問(wèn)題等價(jià)于在n×n格的棋盤(pán)上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線(xiàn)上。1234567812345678QQQQQQQQ對(duì)于有4個(gè)皇后的4*4的棋盤(pán)，求所有的放置方法有多少種？解的表示：用(x11,x21)，(x12,x22)，(x13,x23)，(x14,x24)表示4個(gè)點(diǎn)坐標(biāo)，1≤xij≤4。同時(shí)處理橫坐標(biāo)和縱坐標(biāo)需考慮因素多，算法復(fù)雜行號(hào)固定，用(1,x1)，(2,x2)，(3,x3)，(4,x4)表示4個(gè)皇后的位置。

簡(jiǎn)記為：(x1,x2,x3,x4),1≤xi≤4(i=1,2,3,4)。所有可能的解共44種。約束條件的表示：不在同一行：自然滿(mǎn)足不在同一列：xi≠xj；不在同一主對(duì)角線(xiàn)上：xi-i≠xj-j；不在同一負(fù)對(duì)角線(xiàn)上：xi+i≠xj+j。約束條件可以整合改寫(xiě)為：abs(xi-xj)≠abs(i-j)or(xi≠xj)原問(wèn)題即：尋找符合約束條件的解。算法應(yīng)滿(mǎn)足：沒(méi)有漏網(wǎng)之魚(yú)、不能重復(fù)、速度盡量快回溯（以4皇后為例）解向量：(x1,x2,x3,x4)，1≤xi≤4(i=1，2，3，4)約束：abs(xi-xj)≠abs(i-j)or(xi≠xj)。問(wèn)題的解空間：共44個(gè)解空間樹(shù)：

排列樹(shù)

子集樹(shù)解空間樹(shù)：子集樹(shù)●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●………………●●●●●●●21341234123412341234解空間樹(shù)遍歷：●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●………………●●●●●●●能放則放，不能放則換，不能換則退遞歸回溯：defPlace(k):#判斷k位置能不能放棋子

forjinrange(1,k):ifabs(k-j)==abs(x[j]-x[k])orx[j]==x[k]:returnFalsereturnTruedefBacktrack(t):globalsumift>n:#遞歸出口到達(dá)葉子節(jié)點(diǎn)

sum+=1foriinrange(1,n+1):print("({},{})".format(i,x[i]),end='')print()else:foriinrange(1,n+1):x[t]=iifPlace(t):Backtrack(t+1)#深度優(yōu)先搜索解向量：(x1,x2,…,xn)顯約束：xi=1,2,…,n隱約束：1)不同列：xi

xj2)不處于同一正、反對(duì)角線(xiàn)：|i-j|

|xi-xj|回溯：排列樹(shù)defPlace(k):#判斷是否放在k位置

forjinrange(1,k):ifabs(k-j)==abs(x[j]-x[k]):#剪枝函數(shù)判斷是否在左右斜對(duì)角線(xiàn)上

returnFalsereturnTruedefBacktrack(t):globalsumift>n:#遞歸出口

sum+=1foriinrange(1,n+1):print("({},{})".format(i,x[i]),end='')print()else:foriinrange(t,n+1):x[i],x[t]=x[t],x[i]ift==1orPlace(t):Backtrack(t+1)#深度優(yōu)先搜索

x[i