八皇后问题(python 生成器)

2023-01-31 02:01:14 python 生成器 皇后

问题:

在8×8格的国际象棋上摆放八个皇后,使其不能互相***,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。大致是下面这种样式:

e

思路:

第一步:皇后位置存放问题

用列表或元组表示。索引表示皇后所在的横行。列表的值表示 皇后的 竖列。

那么皇后位置可表示为: L[i]  i in range(8) 且 len(L) =8

第二步:冲突问题。

这种情况,没有考虑到冲突问题:

同一行,由于用索引 表示,所以不会起冲突。

同一行, L[n] 等于 L[i] 值。也或是说 :皇后a. 列表值 - 皇后b.列表值 = 0

斜行问题:

斜行有两个方面考虑,一种是正斜45度,一种是反斜45度。

相当于汉字中的撇捺。但不管那种情况。如果两个皇后是同斜行,必然是这样:

| 皇后a.行值 - 皇后b.行值  | == | 皇后a.列值 - 皇后b. 列值  |

绝对值【皇后a.索引-皇后b.索引 】= 绝对值 【皇后a.列表值 - 皇后b.列表值。】 。如下图所示:

2

设计处理模型:

第一步:皇后摆放顺序 。伪代码为说明:(假设总的要摆放皇后的个数为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[i]  -- pos == 0

斜着冲突: 行值 差等于 列值差的绝对值 。即

| status[i] – pos | =  len(status)  - i

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

    nextY = len(status)        # 当前行号

    for i in range( nextY ):       # 已存在的位置都要比较
        if  abs(status[i] - 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[i] - pos ) in (0, nextY - i ):
            return True 
    return 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
  

相关文章