碼齡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）

耗時太長，等我繼續優化吧