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

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

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

排列樹

子集樹解空間樹：子集樹●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●………………●●●●●●●21341234123412341234解空間樹遍歷：●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●………………●●●●●●●能放則放，不能放則換，不能換則退遞歸回溯：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)不處于同一正、反對角線：|i-j|

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

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

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