问题描述
给定一个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))#排列黑白皇后。 |
结语
回溯算法最大的难点就是找到回退或者继续前进的条件,然后找到递归的出口递归的开始条件,对于运用回溯算法的问题,可以通过特殊的简单的案列结合图形的帮助来模拟回溯的步骤,再将特殊推广到普遍。