Python基于回溯法子集樹模板實(shí)現(xiàn)8皇后問題
更新時(shí)間：2017年09月01日 08:58:08 作者：羅兵
這篇文章主要介紹了Python基于回溯法子集樹模板實(shí)現(xiàn)8皇后問題,簡單說明了8皇后問題的原理并結(jié)合實(shí)例形式分析了Python回溯法子集樹模板解決8皇后問題的具體實(shí)現(xiàn)技巧,需要的朋友可以參考下
本文實(shí)例講述了Python基于回溯法子集樹模板實(shí)現(xiàn)8皇后問題。分享給大家供大家參考，具體如下：
問題
8×8格的國際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
分析
為了簡化問題，考慮到8個(gè)皇后不同行，則每一行放置一個(gè)皇后，每一行的皇后可以放置于第0、1、2、...、7列，我們認(rèn)為每一行的皇后有8種狀態(tài)。那么，我們只要套用子集樹模板，從第0行開始，自上而下，對每一行的皇后，遍歷它的8個(gè)狀態(tài)即可。
代碼：
'''
8皇后問題
'''
n = 8
x = [] # 一個(gè)解（n元數(shù)組）
X = [] # 一組解
# 沖突檢測：判斷 x[k] 是否與前 x[0~k-1] 沖突
def conflict(k):
global x
for i in range(k): # 遍歷前 x[0~k-1]
if x[i]==x[k] or abs(x[i]-x[k])==abs(i-k): # 判斷是否與 x[k] 沖突
return True
return False
# 套用子集樹模板
def queens(k): # 到達(dá)第k行
global n, x, X
if k >= n: # 超出最底行
#print(x)
X.append(x[:]) # 保存（一個(gè)解），注意x[:]
else:
for i in range(n): # 遍歷第 0~n-1 列（即n個(gè)狀態(tài)）
x.append(i) # 皇后置于第i列，入棧
if not conflict(k): # 剪枝
queens(k+1)
x.pop() # 回溯，出棧
# 解的可視化（根據(jù)一個(gè)解x，復(fù)原棋盤。'X'表示皇后）
def show(x):
global n
for i in range(n):
print('. ' * (x[i]) + 'X ' + '. '*(n-x[i]-1))
# 測試
queens(0) # 從第0行開始
print(X[-1], '\n')
show(X[-1])
效果圖
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》
希望本文所述對大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
Python實(shí)現(xiàn)統(tǒng)計(jì)文本中的字符數(shù)量
這篇文章主要為大家詳細(xì)介紹了如何利用Python實(shí)現(xiàn)統(tǒng)計(jì)文本中的字符數(shù)量，包括中/英文字符、數(shù)字、特殊字符等，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-05-05
這篇文章主要介紹了Jupyter加載文件的實(shí)現(xiàn)方法，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-04-04
本文主要介紹了OpenCV仿射變換的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
python 中不同包 類 方法 之間的調(diào)用詳解
這篇文章主要介紹了python 中不同包 類 方法 之間的調(diào)用詳解，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-03-03
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)趣味圖片字符化，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-04-04
這篇文章主要介紹了快速解決cv2.imread()讀取圖像為BGR的問題，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-03-03
這篇文章主要介紹了關(guān)于Python自動化操作Excel, Python 是一種功能強(qiáng)大的編程語言，可以用于許多任務(wù)，包括處理 Excel 文件,需要的朋友可以參考下2023-04-04
TensorFlow神經(jīng)網(wǎng)絡(luò)優(yōu)化策略學(xué)習(xí)
這篇文章主要介紹了TensorFlow神經(jīng)網(wǎng)絡(luò)優(yōu)化策略2018-03-03
這篇文章主要介紹了Python解決走迷宮問題算法,結(jié)合實(shí)例形式分析了Python基于二維數(shù)組的深度優(yōu)先遍歷算法解決走迷宮問題相關(guān)操作技巧,需要的朋友可以參考下2018-07-07
python中有許多有用的庫，要使用這些第三方庫，需要安裝pip。這篇文章主要為大家介紹了pip的安裝與使用，解決pip下載速度慢的問題，需要的可以參考一下2022-07-07