算法設計與分析回溯法—n皇后問題信息工程大學國家級實驗教學示范中心計算機學科組規劃教材算法設計與分析Python案例詳解微課視頻版問題描述：在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。1234567812345678QQQQQQQQ對于有4個皇后的4*4的棋盤，求所有的放置方法有多少種？解的表示：用(x11,x21)，(x12,x22)，(x13,x23)，(x14,x24)表示4個點坐標，1≤xij≤4。同時處理橫坐標和縱坐標需考慮因素多，算法復雜行號固定，用(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；不在同一負對角線上：xi+i≠xj+j。約束條件可以整合改寫為：abs(xi-xj)≠abs(i-j)or(xi≠xj)原問題即：尋找符合約束條件的解。算法應滿足：沒有漏網之魚、不能重復、速度盡量快回溯（以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:#遞歸出口到達葉子節點

sum+=1foriinrange(1,n+1):print("({},{})".format(i,x[i]),end='')print()else:foriinrange(1,n+1):x[t]=iifPlace(t):Backtrack(t+1)#深度優先搜索解向量：(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]):#剪枝函數判斷是否在左右斜對角線上

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)#深度優先搜索

x[i