今天突然有個行外的朋友扔了一張圖給我，希望我能幫他用python做一下這個作業——八皇后問題。

八皇后問題是一種經典的數學求解問題，規則是在8×8的國際象棋棋盤上，要求在每一行(或者每一列)放置一個皇后，且能做到在水平方向、豎直方向和斜方向都沒有沖突。

關于這個問題的編程實現，首先我們將棋盤等價于一個8×8的矩陣(二維數組)，矩陣中的點(x，y)指代棋盤第x行y列的位置。而沖突的自然語言定義是同行、同列或同對角線，那么這個邏輯換算到程序中，我們可以認為兩點(x1，y1)和(x2，y2)至少滿足以下四個條件之一：

同行：x1 = x2

同列：y1 = y2

斜線正方向：x1 + y1 = x2 + y2

斜線反方向：x1 - y1 = x2 - y2

一開始看到這個問題的規則，我有些小瞧了它的難度，以為通過逐行排除過濾就可以推出可行解，因此稍微整理一下思路就草草開干了，最后毫無疑問地踩了不少坑。在這個問題上，逐行定點的方式是可行的，關鍵在于八皇后問題在這種求解方式下存在死解，即可能在中途某行進行取點時，發現該行上沒有一個點符合要求。因此，八皇后問題的程序求解歸根到底其實是一個回溯遍歷的問題。通過回溯，我重新調整了思路：

1、從第一行開始，按照沖突規則過濾出每行目前可選的位置點集合，取一點；

2、如果遇到死解，即當前行沒有符合要求的可選點，則回退到上一行，重新取點；

3、直到第八行取到了符合要求的安全位置，求解成功。

捋清了這個編程思路，利用python實現也就不難了。

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]

# 在后續過程中保存本行過濾完的可選位置

alternative = []

if len(placePicked) != 0:

# 遍歷本行的每一項

for column in row:

# 這個變量標志了該位置是否可用，初始化的時候是False，可用

available = True

# 遍歷已被選的位置

for item in placePicked:

# 只要有一個出現同列或同對角線，或位于排除項列表中時，將available標記為不可用

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

# 該位置可用，添加進可用項數組里

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

# 根據最終結果用圖表展示出來

# 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:

# 沒有遇到死解，繼續往下

row += 1

else:

# 遇到了死解，回退到上一行并且將死解的點存入排除項中，重新選點

row -= 1

exclusions[row].append(placePicked.pop())

# 由于是自上而下選點的方式，當上一行的點重新選取時，后一行的排除項已經沒有意義了，清空

if row < 7:

exclusions[row+1] = []

# 打印出棋盤

print(generate_figure(placePicked))

最終結果如下：

$ python eight_queens.py

- - - x - - - -

- - - - - - - x

- - - - x - - -

- - x - - - - -

x - - - - - - -

- - - - - - x -

- x - - - - - -

- - - - - x - -

總結

以上是生活随笔為你收集整理的八皇后问题python_python求解八皇后问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。