Python|回溯算法解n皇后问题
欢迎点击「算法与编程之美」↑关注我们！
本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。
欢迎加入团队圈子！与作者面对面！直接点击！
问题描述
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
解决方案
思路分析
先讨论n个皇后放在n*n的棋盘中，且不能同行、同列、同对角线的问题，那么第一个条件就是这些皇后的位置需要在不同行，即每行一个皇后。剩下的两个限制条件不妨用以下4*4的棋盘模拟展示（用Q代表皇后）：
当选择第一个位置放置皇后时：
回溯算法大致思路：当一条路可以前进时就一直前进，行不通则退回上一步，以此类推。
当选择（1，1）作为起始皇后的位置时，那么第二排就有两个位置可以选择（2，3）、（2，4），但是当选择（2，3）时，第三排就无法继续了，现在退回去选择（2，4），在第三排hi有一种选择（3，2），在选择了这一点之后，发现第四排已经无法继续了，而且也无法再向第三排后退，说明（1，1）这一点无法作为皇后的位置，上述过程就是本题的一个回溯过程。以此类推，可以发现（1，2）和（1，3）两个点可以作为皇后的起点。
由于每个皇后占一行，所以可以用一个列表来存储每个皇后的所在列，对于上述4*4的棋盘，当选择（1，2）作为起点时，列表可以表示为[2,4,1,3],当选择（1，3）作为起点时，列表可以表示为[3,1,4,2]。同理可以得到n*n棋盘的可行列表。
首先定义一个判断可行位置的函数，分三种情况讨论；
然后开始定义选择棋盘函数，当位置满足判断函数时，把该位置加入到棋盘中，开始递归，递归终止的条件就是每个皇后都找到位置，然后将棋盘加入列表中。
回到本题，找出了可行棋盘也就求出了皇后位置的摆放方法总数，然后在进行排列（由于是黑白两种皇后故排列时有顺序）。
python代码
|
def feasible_index(box, nextx): # box是一个存放每一行皇后位置的横坐标(即每个皇后所在列)，nestx表示下个皇后的横坐标 if len(box)>0: if nextx in box:#第一种情况，下一个皇后的位置位于其他皇后位置的同一列 return False elif nextx==box[-1]-1:#第二种情况，下一个皇后的位置位于上一个皇后的左对角线 return False elif nextx==box[-1]+1:#第三种情况，下一个皇后的位置位于上一个皇后的右对角线 return False return True # 满足位置条件，返回True def queen(feasible_box, n, ans): if len(feasible_box) == n: # 当n个皇后都找到位置后，递归结束 ans.append(feasible_box) # 将可行棋盘加到ans列表中 else: for i in range(n): # 皇后没排完，开始在下一行加入皇后 if feasible_index(feasible_box, i): # 判断i位置是否可行 queen(feasible_box + [i], n, ans) # 将可行的i位置加入棋盘feasible_box，然后递归 lis = [] queen([], 4, lis) if len(lis)<2: print(0) else: print(len(lis)*(len(lis)-1))#排列黑白皇后。 |
结语
回溯算法最大的难点就是找到回退或者继续前进的条件，然后找到递归的出口递归的开始条件，对于运用回溯算法的问题，可以通过特殊的简单的案列结合图形的帮助来模拟回溯的步骤，再将特殊推广到普遍。
END
主 编 | 王文星
责 编 | 黄章鱼
where2go 团队
微信号：算法与编程之美
长按识别二维码关注我们!
温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！