今天突然有個行外的朋友扔了一張圖給我，希望我能幫他用python做一下這個作業(yè)——八皇后問題戒良。
八皇后問題是一種經(jīng)典的數(shù)學(xué)求解問題谋逻，規(guī)則是在8×8的國際象棋棋盤上，要求在每一行(或者每一列)放置一個皇后染苛，且能做到在水平方向鹊漠、豎直方向和斜方向都沒有沖突。
關(guān)于這個問題的編程實現(xiàn)，首先我們將棋盤等價于一個8×8的矩陣（二維數(shù)組）躯概，矩陣中的點（x登钥，y）指代棋盤第x行y列的位置。而沖突的自然語言定義是同行楞陷、同列或同對角線怔鳖，那么這個邏輯換算到程序中，我們可以認(rèn)為兩點（x1固蛾，y1）和（x2结执，y2）至少滿足以下四個條件之一：
同行：x1 = x2
同列：y1 = y2
斜線正方向：x1 + y1 = x2 + y2
斜線反方向：x1 - y1 = x2 - y2
一開始看到這個問題的規(guī)則，我有些小瞧了它的難度艾凯，以為通過逐行排除過濾就可以推出可行解献幔，因此稍微整理一下思路就草草開干了，最后毫無疑問地踩了不少坑趾诗。在這個問題上蜡感，逐行定點的方式是可行的，關(guān)鍵在于八皇后問題在這種求解方式下存在死解恃泪，即可能在中途某行進(jìn)行取點時郑兴，發(fā)現(xiàn)該行上沒有一個點符合要求。因此贝乎，八皇后問題的程序求解歸根到底其實是一個回溯遍歷的問題情连。通過回溯，我重新調(diào)整了思路：
1览效、從第一行開始却舀，按照沖突規(guī)則過濾出每行目前可選的位置點集合，取一點锤灿；
2挽拔、如果遇到死解，即當(dāng)前行沒有符合要求的可選點但校，則回退到上一行螃诅，重新取點；
3状囱、直到第八行取到了符合要求的安全位置州刽，求解成功。
捋清了這個編程思路浪箭，利用python實現(xiàn)也就不難了穗椅。
import random
import math
# 棋盤初始化
# params
# -d: 矩陣的大小
def initial_chessboard(d):
chessboard = [[(x+1, y+1) for y in range(d)] for x in range(d)]
return chessboard
# 指定行過濾出可選位置并隨機選取一個，作為本行queen的填入位置
# params
# -chessboard：棋盤矩陣
# -rowIndex: 指定矩陣的某一行的序號
# -placePicked：已被選的位置
# -exclusions: 回溯時的排除項列表
def filter_and_pick_place(chessboard, rowIndex, placePicked, exclusions):
# 取到該行
row = chessboard[rowIndex]
# 在后續(xù)過程中保存本行過濾完的可選位置
alternative = []
if len(placePicked) != 0:
# 遍歷本行的每一項
for column in row:
# 這個變量標(biāo)志了該位置是否可用奶栖，初始化的時候是False匹表，可用
available = True
# 遍歷已被選的位置
for item in placePicked:
# 只要有一個出現(xiàn)同列或同對角線门坷，或位于排除項列表中時，將available標(biāo)記為不可用
if column[1] == item[1] or column[0]+column[1] == item[0]+item[1] or \
column[0]-column[1] == item[0]-item[1] or column in exclusions:
available = False
# 該位置可用袍镀，添加進(jìn)可用項數(shù)組里
if available:
alternative.append(column)
else:
alternative = row
if len(alternative) == 0:
# 死解默蚌，返回0，指示不成功
return 0
else:
# 活解苇羡，隨機挑選位置點绸吸，返回1，指示成功
randomIndex = math.floor(len(alternative) * random.random())
pick = alternative[randomIndex]
placePicked.append(pick)
return 1
# 根據(jù)最終結(jié)果用圖表展示出來
# params
# -positions: 最終挑選的位置列表
def generate_figure(positions):
figureSring = ''
for row in range(8):
for col in range(8):
if (row+1, col+1) in positions:
figureSring += 'x '
else:
figureSring += '- '
figureSring += '\n'
return figureSring
if __name__ == '__main__':
chessboard = initial_chessboard(8)
placePicked = []
exclusions = [[] for i in range(8)]
row = 0
while row < 8:
success = filter_and_pick_place(chessboard, row, placePicked, exclusions[row])
if success == 1:
# 沒有遇到死解设江，繼續(xù)往下
row += 1
else:
# 遇到了死解锦茁，回退到上一行并且將死解的點存入排除項中，重新選點
row -= 1
exclusions[row].append(placePicked.pop())
# 由于是自上而下選點的方式叉存，當(dāng)上一行的點重新選取時码俩，后一行的排除項已經(jīng)沒有意義了，清空
if row < 7:
exclusions[row+1] = []
# 打印出棋盤
print(generate_figure(placePicked))
最終結(jié)果如下：
$ python eight_queens.py
- - - x - - - -
- - - - - - - x
- - - - x - - -
- - x - - - - -
x - - - - - - -
- - - - - - x -
- x - - - - - -
- - - - - x - -
