八皇后问题（python 生成器）

yadianna

问题：
  在8×8格的国际象棋上摆放八个皇后，使其不能互相***，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。大致是下面这种样式：
  
  思路：
　　第一步：皇后位置存放问题
　　用列表或元组表示。索引表示皇后所在的横行。列表的值表示 皇后的 竖列。
　　那么皇后位置可表示为： L  i in range(8) 且 len(L) =8
　　第二步：冲突问题。
　　这种情况，没有考虑到冲突问题：
　　同一行，由于用索引 表示，所以不会起冲突。
　　同一行， L[n] 等于 L 值。也或是说 ：皇后a. 列表值 - 皇后b.列表值 = 0
　　斜行问题：
　　斜行有两个方面考虑，一种是正斜45度，一种是反斜45度。
　　相当于汉字中的撇捺。但不管那种情况。如果两个皇后是同斜行，必然是这样：
　　| 皇后a.行值 - 皇后b.行值  | == | 皇后a.列值 - 皇后b. 列值  |
　　绝对值【皇后a.索引-皇后b.索引 】= 绝对值 【皇后a.列表值 - 皇后b.列表值。】 。如下图所示：

设计处理模型：
  第一步：皇后摆放顺序 。伪代码为说明：(假设总的要摆放皇后的个数为num =8 )
　　以上图为例，皇后按 行 一个一个摆放。

　　当摆放第N+1个时，整个棋盘状态： next = N+1

  

　　已摆放的位置放在列表 status 中： len ( status ) == N 。

  

　　第 N+1 个，能摆放的位置 是   range( num )。 for pos in range( num )

　　但是，这里需要排除 起冲突的。
# 第N+1 个皇后能摆放的位置：　　

# 此时：皇后位置列表：status,已摆放：len(status)　　

    for pos in range(num):if not drop_place(pos,status):    # 如果没有冲突继续摆放，否则返回。　　

第二步：排除冲突。
　　每一个已摆放好位置的皇后都要与第 N+1 个皇后 做比较，

　　for i in range(N):   第 i  行。

　　列值冲突  ，相等：  status  -- pos == 0

　　斜着冲突： 行值 差等于 列值差的绝对值 。即
　　| status – pos | =  len(status)  - i

#  pos 表示当前位置， status 表示前面摆放位置　　
def drop_place(pos,status):
　　

　　nextY = len(status)        # 当前行号
　　

　　for i in range( nextY ):       # 已存在的位置都要比较
　　if  abs(status - pos ) in (0, nextY - i ):     #如果有位置冲突
　　return True           # 直接返回冲突，否则继续比较
　　return False           # 最后一个比较完，没有冲突返回 False.注意缩进
　　

第三步,是否继续摆放:

　　这时需要考虑的是,本次摆放 的是不是 最后一个位置。
　　如果不是，那继续摆放。（递归摆放）
　　如果是最后一个位置.即 num –1. 如果是 那么是返回 pos 位置 还是 pos + status呢？
　　和第一个代码结合 ：

def queens(num=8, status=[]):for pos in range(num):if not drop_place(pos,status):# 下面是继续摆放　　if len(status) != num -1:
　　for each in queens(num,status+[pos,]): # 第一个？号
　　yield [pos,]+each                   # 第二个？号
　　

　　else:        # 最后一个
　　yield [pos,]                          # 第三个？号
　　

　　这里要解释下，为什么使用迭代生成器 而 不用 return。
　　第N 个皇后摆放时，有 range(num) 个位置。如果，使用 return，那么当第一个位置满足条件时，直接返回。我们这里需要的是所有满足摆放的位置。
　　位置是多个，所以 ，这里使用  for each in queens(num, status +[pos,]) . each 表示第 N+2 个皇后 满足 不冲突的位置。
　　status + [pos,] 表示当 添加 N+2 个皇后时，此时队列必须要加上N+1的位置。
　　第二个问号： 这里 为什么 用 生成 器 而不用 return ，就像我们上面说的那样，要生成所有满足 条件 的N+2位置，而不是一个位置就返回。
　　再看返回的队列，[pos,] + each.
　　这里 ，要再回想回想 递归的要求，必须是 递归的条件一步步满足停止递归的要求，否则递归 就是无限循环。
　　这里，我们要摆放完所有的皇后，必须是基于最后一个皇后的位置存在，然后，倒着存入 所有的位置。
　　而在摆放第N+2个皇后时，能确认的只有，pos + each 位置。
　　当 each = 最后一个皇后时，就会从最后一个位置反着添加所有皇后的位置，从而生成整个符合条件的位置。
　　第三个问号： 递归到最后一个皇后时，依然需要 使用 for each in queens(num, status+[pos,]) 得到最后一们的位置迭代对象。
　　所以，这里使用 yield 返回 [pos,]，再依次相加。最后，得到符合条件的一列数组。
　　大致代码如下：
def drop_place(pos,status):　　nextY
= len(status)for i in range( nextY ):if  abs(status - pos ) in (0, nextY - i ):return Truereturn False　　

　　

def queens(num=8, status=[] ):for pos in range(num):if not drop_place(pos,status):if len(status) == num - 1:yield [pos,]else:for result in queens(num, status +[pos,]):yield [pos,]+result　　

　　

print( len(list(queens(8))) )　　

# 显示的长度为 92