码龄0.3年的python成长之路（五）：八皇后、16皇后

问题描述

有一个8x8的棋盘，需要摆8个皇后在棋盘上，让8个皇后分别不相见。问：有多少种摆法。知道8皇后怎么解决，自然就解决了n皇后问题。

思考

• 这个题目也是CSDN一抓一大把的解答，在力扣上，这个题目也是难度中上的，大多数人用的是DFS算法，有没有不用算法的解，能破8皇后的局？
• 这道题的解答，将体现出人脑和机器脑的比例。比如，你设规则从第一行开始摆皇后，这就是给机器一个限制。如果你这么设置了，那么最后得到的摆法个数恐怕要乘以4。因为有方向性的摆法，转四次，会有不一样的结局。给你们看看八皇后的一个案例，转几下，是不是不一样。

  

• 这意味着，很多人的计算方法是可能是不够（也有人是冗余）的。
• 所以，我们试着更新方法，放宽人对机器的限制试试

更新方法

• 用 n = 8 来建立棋盘数组boardlist，数组里的每一个元素，都是【行，列】坐标；
• 定义落下一个皇后，会“占据”或“无效化"那些坐标，定义为taken列表，并实时更新boardlist；

• 准备100000个皇后随机往下丢

  – 判断是否可以落子：随机行列数是不是在boardlist中；

  ——>在：落子，执行落下后更新的taken和boardlist

  ——>不在：返回，继续丢，反正我们皇后多的是

  – 条件判断：如果boardlist在某个时刻变空，无法再摆皇后了。

  ——>如果此时在盘皇后为n，如果这个组合从未被记录，则记录这个组合

  ——>记录或者不记录，这个时刻都要更新Boardlist和相关的动态变量

• 最后我们会获得一个很杂乱的组合，同样的组合，就算是排序不一样，也会被记录，所以需要数据清洗。
• 清洗后的，就是我们要的答案。
• 完毕

代码实现

• 所用的库

import numpy as np
import random
import time
from operator import itemgetter
           

numpy大家都知道，是做数组的运算需要的

random是随机用法的库

time用来计算程序花多少时间执行

operator是拿来给我按照列表中某个元素排序用的

• 初始数据

n = 8
taken = []  # 棋盘上已经占用了的行列数组
nums = list(set(np.arange(1, n+1)))    # 1到n的数字列表
queen = []
           

• 生成棋盘数组

def board():
    boardlist = []
    for row in range(1, n+1):
        for col in range(1, n+1):
            a = [row, col]
            boardlist.append(a)
    return boardlist
boardlist = board()   # 棋盘上所有的行列数组(list)
           

• 定义落下一个伟大的皇后，棋盘上会无效化多少格子（taken），以及实时更新棋盘（boardlist）

def oneQ(row, col):
    queen.append([row, col])
    for i in range(1, n+1):
        taken.append([row, i])  # 占用整行
        taken.append([i, col])  # 占用整列
        if row+i <= n and col-i >= 0:     
            taken.append([row+i, col-i])    
        if row-i >= 0 and col+i <= n:
            taken.append([row-i, col+i])  # 占用副对角线
        if row-i >= 0 and col-i >= 0:
            taken.append([row-i, col-i])
        if row+i <= n and col+i <= n:
            taken.append([row+i, col+i])  # 占用主对角线
    for j in taken:
        if j in boardlist:
            boardlist.remove(j)   # 棋盘上减去占用的部分
    return taken, boardlist, queen
           

• 写到这里，我们试验一下

print(oneQ(3,4)) # 假设落子再（3，4）上
# 已占用taken: 
# [[3, 1], [1, 4], [4, 3], [2, 5], [2, 3], [4, 5], [3, 2],
#  [2, 4], [5, 2], [1, 6], [1, 2], [5, 6], [3, 3], [3, 4],
#  [6, 1], [0, 7], [0, 1], [6, 7], [3, 4], [4, 4], [7, 0],
#  [7, 8], [3, 5], [5, 4], [3, 6], [6, 4], [3, 7], [7, 4],
#  [3, 8], [8, 4]]
# 更新棋盘boardlist:
# [[1, 1], [1, 3], [1, 5], [1, 7], [1, 8], [2, 1], [2, 2],
#  [2, 6], [2, 7], [2, 8], [4, 1], [4, 2], [4, 6], [4, 7],
#  [4, 8], [5, 1], [5, 3], [5, 5], [5, 7], [5, 8], [6, 2],
#  [6, 3], [6, 5], [6, 6], [6, 8], [7, 1], [7, 2], [7, 3],
#  [7, 5], [7, 6], [7, 7], [8, 1], [8, 2], [8, 3], [8, 5],
#  [8, 6], [8, 7], [8, 8]]
# 记录已放皇后的位置queen: [[3, 4]]
           

完美

• 开始摆盘，巨量的皇后准备入场，为了大家看得懂，我注释比较多

def fullboard():
    global taken, boardlist, queen, nums
    counts = 0
    done = []
    for i in range(100000):   # 准备10万个皇后
        row_ = random.sample(nums, 1)  # 在nums里随机选一个
        for i in row_:
            row = i
        col_ = random.sample(nums, 1)  # 在nums里随机选一个
        for j in col_:
            col = j    # int化数字，否则row和col都是list
        if boardlist != []:  
            if [row, col] in boardlist:  # 确定行列可下
            # 确定落子
                taken, boardlist, queen = oneQ(row, col)  # 更新落子一次后的数据
                counts += 1  # 记录落子+1            
        else: # boardlist == []
            # 判断boardlist空集就记录和重置棋盘、相关动态变量
            if counts == n:  # 将能摆盘的进行记录
                if queen not in done:
                    done.append(queen)  # 记录入done列表
            # 然后重置所有数据，迎接新的皇后降临
            boardlist = board()   # 棋盘上所有的行列数组(list)
            taken = []  # 全部归位
            queen = []
            counts = 0
    return done  
           

返回的是done，也就是最后摆盘8个皇后成功的所有方案。

• 清洗我们的done，获取最后数据data

done = fullboard()
for i in done:
    i.sort(key = itemgetter(0), reverse = False) # 先排序，才能判断重复即冗余
data = [] # 最终要的清洗后数据
for i in done:
    if i not in data:
        data.append(i)
np.save('data.npy', data) # 转存为npy文档，这样读取的时候比较有格式，看得清
           

• 我们观察n=4，也就是4个皇后，4x4棋盘的结果

# np.save('data.npy', data)  存过一次的可以注释掉
data = np.load('data.npy') # 如果不行就改成绝对路径
print('方案分别是：{}'.format(data))
print('方案个数为：{}'.format(len(data)))
方案分别是：
[[[1 2]
  [2 4]
  [3 1]
  [4 3]]

 [[1 3]
  [2 1]
  [3 4]
  [4 2]]]
方案个数为：2
计算用时：0.8757秒
           

• 8 皇后的摆法，尝试不断增加备用皇后的数量，反正有清洗数据的方法在，不会产生冗余，可以试到方案数稳定。

8个皇后的摆法，10万个皇后
方案个数为：49
计算用时：1.7458秒
           

8个皇后的摆法，100万个皇后
方案个数为：92
计算用时：17.7233秒
           

8个皇后的摆法，1000万个皇后
方案个数为：92
计算用时：181.0013秒
           

总结

• 8皇后的问题困扰了我很久很久，上述方法已经是不用高大上的算法可以实现的、人脑最少、绝大利用机器算力的最简单方法。
• 我们如果把92除以4看看，可能最简化的摆放方法，只有23种。

还有优化空间吗？16皇后试着算算？

• 比如在放queen方案进入done之前，我们可以先进行排序，这样就不用后来的清洗整理。就像是你将土豆一个个洗了放进篮子，还是先把带泥土豆都放进篮子，再统一清洗的区别。我把修改处放在下面。

def fullboard():
    ......    
        else: # boardlist == []
            # 判断boardlist空集就记录和重置棋盘、相关动态变量
            if counts == n:  # 将能摆盘的进行记录
                queen.sort(key = itemgetter(0), reverse = False)
                # 提前排序（先清洗再放入，减少数据处理量）
                if queen not in done:
                    done.append(queen)  # 记录入done列表
           

• 调整前后是否会更快？试试100万皇后，做一次8皇后的

方案个数为：92
计算用时：18.3677秒
改之前————计算用时：17.7233秒
           

看起来，还是一起洗土豆比较有效率，哈哈哈。

• 一个个洗土豆，尝试16皇后：

10万皇后：
方案个数为：2
计算用时：6.9090秒
           

100万皇后：
方案个数为：15
计算用时：65.7159秒
           

1000万皇后：
方案个数为：145
计算用时：665.4434秒
           

• 统一洗数据，生成npy的方法，看看10000万（1个亿）皇后（16皇后问题），大家不要轻易试，挺耗时间，除非你默认GPU计算（我烧的是CPU）

耗时太长，等我继续优化吧