算法设计与分析 课件 7.10-回溯法 - 典型应用 - 两种实现 - n皇后问题

算法设计与分析回溯法—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