文章目錄
- 1 八皇後問題
- 2 程式代碼
-
- 2.1 程式1
- 2.2 程式2
- 2.3 程式3
-
- 2.3.1 爬山法
- 2.3.2 随機重新開機爬山法
- 2.3.3 允許皇後側移的爬山法
- 3 評價
1 八皇後問題
有一個8乘8的棋盤，現在要将八個皇後放到棋盤上，滿足：對于每一個皇後，在自己所在的行、列、兩個對角線都沒有其他皇後。
不了解爬山法、随機重新開機爬山法、允許側移的爬山法的話，請看這裡。
規定棋盤的同列隻能出現一個皇後。每一個棋盤，對應于一個長度為8的序列，每一個數的範圍是[1, 8]，第k個數字所代表的含義是第k列中皇後所在的行數，如[3,2,5,4,3,2,1,3]代表棋盤上從第一列到第八列，皇後所擺放的行數分别為第3，2，5，4，3，2，1，3行。任意狀态（包括初始狀态）的所有後繼狀态為【從目前狀态開始，将任意一個皇後移到同列的其他7個格子後的所有狀态】。對于任意一個已有八個皇後的棋盤（當然同一列有且僅有一個皇後）的後繼狀态均有8*7=56個。
2 程式代碼
2.1 程式1
程式1：generate_init_seq.py。如果8個皇後在8*8的棋盤上可以随意擺放，當然是不能在同一個格子裡放超過一個皇後的情況下，本來所有需要測試是否滿足要求的序列共有64*63*…*57=1.78e+14個，這太多了。是以此程式的工作是篩選出那些【每行與每列都隻有一個皇後存在】的序列，這樣的序列有8*7*6*5*4*3*2=40320個，可以大大縮減後續程式的運作時間，而且這樣在後面處理每個序列時隻需要考慮兩條對角線上和所在的行上有沒有其他皇後即可（不用考慮列）。如下：
import json
import time
start = time.time()
seq = [[i, j, k, l, m, n, o, p]
for i in range(1, 9)
for j in range(1, 9)
for k in range(1, 9)
for l in range(1, 9)
for m in range(1, 9)
for n in range(1, 9)
for o in range(1, 9)
for p in range(1, 9)
if all([i != j, i != k, i != l, i != m, i != n, i != o, i != p,
j != k, j != l, j != m, j != n, j != o, j != p,
k != l, k != m, k != n, k != o, k != p,
l != m, l != n, l != o, l != p,
m != n, m != o, m != p,
n != o, n != p,
o != p])] # 篩選出【每行與每列都隻有一個皇後】的序列
print('有' + str(len(seq)) + '個可能的序列')
with open('seq.json', 'w') as file_object:
json.dump(seq, file_object)
end = time.time()
print('Successful!')
print('已将生成的序列存儲到檔案seq.json中，用時' + str('%.2f' % (end - start)) + 's')
輸出如下。注意會生成一個檔案seq.json，我上傳到了csdn上，你可以看看這裡，你也可以運作程式1，就可以在自己電腦上得到一個檔案，除了運作時間有差別，其他輸出和我這個是一樣的：
有40320個可能的序列
Successful!
已将生成的序列存儲到檔案seq.json中，用時17.61s
2.2 程式2
程式2：functions.py。包括兩個函數：attacked_queens_pairs, display_board，分别完成【計算序列對應棋盤的互相攻擊的皇後對數】和【列印輸出序列對應的棋盤】的功能。如下：
import numpy as np
def attacked_queens_pairs(seqs):
"""
計算序列對應棋盤的【互相攻擊的皇後對數n】，0<=n<=28，最優解要滿足n=0
隻需要檢查目前棋盤的八個皇後在各自的行和兩條對角線上是否有其他皇後，不需判斷同列是否有其他皇後
"""
a = np.array([0] * 81) # 建立一個有81個0的一維數組
a = a.reshape(9, 9) # 改為9*9二維數組。為友善後面使用，隻用後八行和後八列的8*8部分，作為一個空白棋盤
n = 0 # 互相攻擊的皇後對數初始化為0
for i in range(1, 9):
a[seqs[i - 1]][i] = 1 # 根據序列，按從第一列到最後一列的順序，在空白棋盤對應位置放一個皇後，生成目前序列對應的棋盤
for i in range(1, 9):
for k in list(range(1, i)) + list(range(i + 1, 9)): # 檢查每個皇後各自所在的行上是否有其他皇後
if a[seqs[i - 1]][k] == 1: # 有其他皇後
n += 1
t1 = t2 = seqs[i - 1]
for j in range(i - 1, 0, -1): # 看左半段的兩條對角線
if t1 != 1:
t1 -= 1
if a[t1][j] == 1:
n += 1 # 正對角線左半段上還有其他皇後
if t2 != 8:
t2 += 1
if a[t2][j] == 1:
n += 1 # 次對角線左半段上還有其他皇後
t1 = t2 = seqs[i - 1]
for j in range(i + 1, 9): # 看右半段的兩條對角線
if t1 != 1:
t1 -= 1
if a[t1][j] == 1:
n += 1 # 正對角線右半段上還有其他皇後
if t2 != 8:
t2 += 1
if a[t2][j] == 1:
n += 1 # 次對角線右半段上還有其他皇後
return int(n/2) # 傳回n/2，因為A攻擊B也意味着B攻擊A，是以傳回n的一半
def display_board(seqs):
"""
顯示序列對應的棋盤
"""
board = np.array([0] * 81) # 建立一個有81個0的一維數組
board = board.reshape(9, 9) # 改變為9*9二維數組，為了後面友善使用，隻用後八行和後八列的8*8部分，作為一個空白棋盤
for i in range(1, 9):
board[seqs[i - 1]][i] = 1 # 根據序列，從第一列到最後一列的順序，在對應位置放一個皇後，生成目前序列對應的棋盤
print('對應棋盤如下:')
for i in board[1:]:
for j in i[1:]:
print(j, ' ', end="") # 有了end=""，print就不會換行
print() # 輸出完一行後再換行，這裡不能是print('\n')，否則會換兩行
此程式無任何輸出，隻是定義了2個函數以供主程式調用。
2.3 程式3
2.3.1 爬山法
程式3：main.py。為主程式，通過調用程式2的兩個函數，完成爬山法解決八皇後問題的全過程。如下：
import json
import random
from functions import attacked_queens_pairs, display_board
with open('seq.json', 'r') as file_object:
seqs = json.load(file_object) # 載入儲存好的序列
current_seqs = random.choice(seqs) # 随機挑選一個序列
print('随機挑選的初始序列為：' + str(current_seqs))
display_board(current_seqs)
while True:
successors = [] # 目前狀态的後繼狀态集合
count = 0 # 計數變量
dicts = [] # 由一個個字典組成的清單，每個字典有兩項内容：序列及對應棋盤互相攻擊皇後對數
a = list(range(1,9))
for item in current_seqs:
for i in a[:item - 1] + a[item:]:
seqs_tmp = list(current_seqs)
seqs_tmp[count] = i
successors.append(seqs_tmp) # 生成目前棋盤的後繼狀态，任意棋盤對應的後繼狀态都有56種
count = count + 1
if count == 8:
break
for s in successors:
tmp_pair = attacked_queens_pairs(s)
dicts.append({'seqs':s, 'attacked_queens_pairs':tmp_pair})
nums = []
for d in dicts:
nums.append(d['attacked_queens_pairs']) # 擷取所有後繼狀态的攻擊的皇後對數，共56個值
mins = min(nums) #取最小的
current_attacked_queens_pairs = attacked_queens_pairs(current_seqs)
if mins >= current_attacked_queens_pairs: # 目前棋盤最好
answer = current_seqs # 算法最終運算結果為目前棋盤
break
temp = []
for d in dicts:
if d['attacked_queens_pairs'] == mins:
temp.append(d['seqs']) # 存儲互相攻擊的皇後對數最少的棋盤，因為可能不止一個，是以用清單存儲
current_seqs = random.choice(temp) # 随機選擇一個棋盤作為目前棋盤
print('------') # 執行這條語句意味着爬山法結束了
if attacked_queens_pairs(answer) == 0:
print('已找到最優解序列：' + str(answer))
display_board(answer)
else:
print('本次搜尋未找到最優解，最好的序列為：' + str(answer))
print('攻擊的皇後對數為'+ str(attacked_queens_pairs(answer)))
display_board(answer)
一種輸出如下：
随機挑選的初始序列為：[8, 3, 2, 7, 6, 4, 5, 1]
對應棋盤如下:
0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0
------
已找到最優解序列：[3, 6, 2, 7, 1, 4, 8, 5]
對應棋盤如下:
0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0
另一種輸出如下：
随機挑選的初始序列為：[2, 1, 6, 8, 5, 3, 4, 7]
對應棋盤如下:
0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
------
本次搜尋未找到最優解，最好的序列為：[3, 1, 6, 8, 5, 2, 4, 7]
攻擊的皇後對數為1
對應棋盤如下:
0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
上面列出了兩種輸出，第一種找到了最優解，第二種找到的是局部最優解。
通常爬山法可以以很快的速度找到問題的解，因為一般從較差的狀态開始擴充是很容易做到的。但是爬山法經常也會陷入局部最優而難以“自拔”，也就是說在算法執行過程中有可能到達這樣一種狀态——在這個狀态下再也做不到更好的改善了。如在解決八皇後問題中，首先從随機生成的一個上面有八個皇後的棋盤開始，使用最陡峭上升的爬山法（steepest-ascent hill climbing）在86%的情況下會陷入局部最優，且僅能在14%的情況下解決問題。爬山法過程比較快，在解決八皇後問題中，平均下來隻需四步便可成功得到解，但是同樣地，在可能在第三步就陷入了局部最優。下面改變政策，使用随機重新開機爬山法改進算法。
2.3.2 随機重新開機爬山法
随機重新開機爬山法的思想：如果一開始沒有成功，那就再試一次，若還沒成功就繼續嘗試。
程式3：main.py。為主程式。如下：
import json
import random
from functions import attacked_queens_pairs, display_board
with open('seq.json', 'r') as file_object:
seqs = json.load(file_object) # 載入儲存好的序列
current_seqs = random.choice(seqs) # 随機挑選一個序列
print('随機挑選的初始序列為：' + str(current_seqs))
display_board(current_seqs)
while True:
successors = [] # 目前狀态的後繼狀态集合
count = 0 # 計數變量
dicts = [] # 由一個個字典組成的清單，每個字典有兩項内容：序列及對應棋盤互相攻擊皇後對數
a = list(range(1,9))
for item in current_seqs:
for i in a[:item - 1] + a[item:]:
seqs_tmp = list(current_seqs)
seqs_tmp[count] = i
successors.append(seqs_tmp) # 生成目前棋盤的後繼狀态，任意棋盤對應的後繼狀态都有56種
count = count + 1
if count == 8:
break
for s in successors:
tmp_pair = attacked_queens_pairs(s)
dicts.append({'seqs':s, 'attacked_queens_pairs':tmp_pair})
nums = []
for d in dicts:
nums.append(d['attacked_queens_pairs']) # 擷取所有後繼狀态的攻擊的皇後對數，共56個值
mins = min(nums) #取最小的
current_attacked_queens_pairs = attacked_queens_pairs(current_seqs)
if mins < current_attacked_queens_pairs: # 後繼狀态更好
temp = []
for d in dicts:
if d['attacked_queens_pairs'] == mins:
temp.append(d['seqs']) # 存儲互相攻擊的皇後對數最少的棋盤，因為可能不止一個，是以用清單存儲
current_seqs = random.choice(temp) # 随機選擇一個棋盤作為目前棋盤
elif current_attacked_queens_pairs != 0: # 目前狀态不是最優解
current_seqs = random.choice(seqs) # 從初始序列集随機重新挑選一個序列
else:
answer = current_seqs # 目前狀态為最優解
break
print('------') # 執行這條語句意味着爬山法結束了
print('已找到最優解序列：' + str(answer))
print('互相攻擊的皇後對數為' + str(attacked_queens_pairs(answer)))
display_board(answer)
一種輸出如下：
随機挑選的初始序列為：[7, 1, 8, 6, 3, 2, 4, 5]
對應棋盤如下:
0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
------
已找到最優解序列：[6, 3, 7, 2, 8, 5, 1, 4]
互相攻擊的皇後對數為0
對應棋盤如下:
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0
算法從随機産生的初始狀态開始，執行一系列的爬山搜尋過程，若沒找到最優解，就再生成一個初始狀态，進行搜尋，直到找到目标時算法才停止。随機重新開機爬山法完備的機率接近于1，即随機重新開機爬山法大多都可以找到解。
2.3.3 允許皇後側移的爬山法
程式3：main.py。為主程式，通過調用程式2的兩個函數，完成允許皇後側移的爬山法解決八皇後問題的全過程。如下：
import json
import random
from functions import attacked_queens_pairs, display_board
with open('seq.json', 'r') as file_object:
seqs = json.load(file_object) # 載入儲存好的序列
current_seqs = random.choice(seqs) # 随機挑選一個序列
print('随機挑選的初始序列為：' + str(current_seqs))
display_board(current_seqs)
while True:
successors = [] # 目前狀态的後繼狀态集合
count = 0 # 計數變量
dicts = [] # 由一個個字典組成的清單，每個字典有兩項内容：序列及對應棋盤互相攻擊皇後對數
a = list(range(1,9))
for item in current_seqs:
for i in a[:item - 1] + a[item:]:
seqs_tmp = list(current_seqs)
seqs_tmp[count] = i
successors.append(seqs_tmp) # 生成目前棋盤的後繼狀态，任意棋盤對應的後繼狀态都有56種
count = count + 1
if count == 8:
break
for s in successors:
tmp_pair = attacked_queens_pairs(s)
dicts.append({'seqs':s, 'attacked_queens_pairs':tmp_pair})
nums = []
for d in dicts:
nums.append(d['attacked_queens_pairs']) # 擷取所有後繼狀态的攻擊的皇後對數，共56個值
mins = min(nums) #取最小的
current_attacked_queens_pairs = attacked_queens_pairs(current_seqs)
if mins < current_attacked_queens_pairs: # 後繼狀态更好
temp = []
for d in dicts:
if d['attacked_queens_pairs'] == mins:
temp.append(d['seqs']) # 存儲互相攻擊的皇後對數最少的棋盤，因為可能不止一個，是以用清單存儲
current_seqs = random.choice(temp) # 随機選擇一個棋盤作為目前棋盤
elif current_attacked_queens_pairs != 0: # 目前狀态不是最優解
a = list(range(8))
pos1 = random.choice(a)
a.remove(pos1)
pos2 = random.choice(a)
current_seqs[pos1],current_seqs[pos2] = current_seqs[pos2],current_seqs[pos1]
else:
answer = current_seqs # 目前狀态為最優解
break
print('------') # 執行這條語句意味着爬山法結束了
print('已找到最優解序列：' + str(answer))
print('互相攻擊的皇後對數為' + str(attacked_queens_pairs(answer)))
display_board(answer)
輸出如下：
随機挑選的初始序列為：[2, 7, 6, 8, 4, 5, 3, 1]
對應棋盤如下:
0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
------
已找到最優解序列：[2, 4, 6, 8, 3, 1, 7, 5]
互相攻擊的皇後對數為0
對應棋盤如下:
0 0 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0
在上述爬山法代碼中，若到達了局部最優狀态時，允許任意一對（并且隻允許一對）皇後橫向移動，例如将第2列和第7列的皇後移入對方行的位置。這種改進方案可以大大提高爬山法解決八皇後問題的成功機率，上述代碼基本上每次運作都可以得到解序列。
3 評價
自己需要補充模拟退火算法的代碼
END
![資訊學奧賽一本通 1214：八皇後 | OpenJudge NOI 2.5 1756:八皇後[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)