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