算法回顾之：递归经典算法-八皇后问题

• 更多分享：http://www.catbro.cn

一、前言

• 说起八皇后问题，它是一个古老而著名的问题，是回溯算法的典型案例。
• 该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，
• 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

二、关键点

从上面的描述我们可以得出，符合八皇后的解须符合下列三个条件：（行为y，列为x表示，也就是一个二维表）

• 1、所有皇后的x不相同
• 2、所有皇后的y不相同
• 3、不在同一对角线上

三、解体思维整理

• 1、所有皇后的x不相同解决方法：
• 很简单：直接用将要摆放的皇后的x与已摆放好的皇后的x对比，相等则冲突
• 2、所有皇后的y不相同解决方法：
• 这个其实可以不用处理，因为解决这个问题的根本就是一行只放一个皇后，当然，如果你转换一下，从列开始，一列一列来访，原理也是一样的，所以我们x和y，只需要处理一个就可以了
• 3、不能处于同一对角线上
• 这个需要点技巧，其实可以这样子,从下面可以分析出，只要Nx-Tx!=Ny-Ty,可以理解为两个方向的距离不能相等，(目前我是这样子理解的，有更好的方法可以留言一起学习哦)

四、编码实现

（突然想用python来编码，我们的python可是非常适合用来处理该类问题的哦，当然你用其他编程语言也是可以的，重要的是理解了解题思路即可）

• 1、我们先编写一个判断新摆放的皇后与已摆放的皇后是否冲突的判断方法：

    #判断是否冲突
    #state这里是用元组来实现，已摆放的皇后的X轴的值会通过state传递进来
    #nextX 表示即将要摆放的皇后的X轴的值
    def conflict(state,nextX):
    	#1）、获取已摆放的皇后的数量
    	nextY = len(state);
    	for i in range(nextY):
    		#2）、
    		tempX = abs(state[i] - nextX);
    		tempY = nextY - i;
    		if tempX in (0,tempY):
    			return True;
    	return False;
  

• 2）处的代码可以这样理解：tempX代表新增皇后老皇后（已摆放的皇后称为老皇后，方便表述，后面的我也会这样称呼哦）在X轴上的距离，tempY为新皇后与老皇后在Y轴上的距离

• if tempX in (0,tempY):就很好理解了，判断tempX是元组（0，tempY）中的两个元素中的一个。为什么是0和tempY呢？

• 0:即X轴的值不能相等，相等不久处于同一列了么？这就冲突了哦

• tmepY：前面解题思维整理有说，其就是保证x轴和Y轴方向上新皇后和老皇后的距离不能相等，相等就处于对角线上了哦

• 2、利用递归调用处理8皇后问题

    #为了调用方便，我们提供了默认值
    def queens(num=8,state=()):
    	for pos in range(num):
    		#1）判断pos是否冲突，pos代表X值
    		if not conflict(state,pos):
    			#2）重点，这里是递归的出口，当我们能够摆放下第8个皇后，也就代表我们之前的摆放策略是可行的
    			if len(state) == num-1:
    				yield (pos,);
    			else:
    				# 如果不是最后一个皇后，就递归调用queens方法
    				for result in queens(num,state+(pos,)):
    					yield (pos,)+result;
  

• 3、为了输出好看，我们增加一个打印方法

    def prettyPrint(solution):
    	def prettyLine(pos,lenght = len(solution)):
    		return 'X'*(pos)+'0'+'X'*(lenght-pos-1);
    	for pos in solution:
    		print(prettyLine(pos));
  

• 4、一切准备就绪，我们来调用一下吧

    for solution in queens():
    	print(solution)
    	prettyPrint(solution)
    	print("----------")
  

• 运行结构，一共有92个，我这里就只截取一个

    (0, 4, 7, 5, 2, 6, 1, 3)
    0XXXXXXX
    XXXX0XXX
    XXXXXXX0
    XXXXX0XX
    XX0XXXXX
    XXXXXX0X
    X0XXXXXX
    XXX0XXXX
  
    ----------
  

• 总结：算法是程序的灵魂，每天进步一点，温故而知新；