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入門類和對象，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
使用fiddler抓包工具Python requests報(bào)錯(cuò):ValueError: check_h
這篇文章主要介紹了使用fiddler抓包工具Python requests報(bào)錯(cuò):ValueError: check_hostname requires server_hostname的解決,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12
在python中實(shí)現(xiàn)將一張圖片剪切成四份的方法
今天小編就為大家分享一篇在python中實(shí)現(xiàn)將一張圖片剪切成四份的方法，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-12-12
Opencv實(shí)現(xiàn)二維直方圖的計(jì)算及繪制
這篇博客將介紹如何使用Opencv進(jìn)行二維直方圖的計(jì)算及繪制，維直方圖可以讓我們對不同的像素密度有更好的了解，感興趣的可以了解一下2021-07-07
這篇文章主要介紹了Python爬蟲網(wǎng)頁元素定位術(shù)，文章通過Beautiful?Soup模塊展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下2022-05-05
這篇文章主要介紹了Python實(shí)現(xiàn)字符串格式化輸出的方法,結(jié)合具體實(shí)例形式總結(jié)分析了Python字符串格式化輸出的各種常用操作技巧,需要的朋友可以參考下2021-10-10
今天小編就為大家分享一篇解決pycharm工程啟動卡住沒反應(yīng)的問題，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-01-01
這篇文章主要介紹了Python反射和內(nèi)置方法重寫,結(jié)合實(shí)例形式較為詳細(xì)的分析了Python反射概念、原理及內(nèi)置方法重寫相關(guān)操作技巧與注意事項(xiàng),需要的朋友可以參考下2018-08-08
python通用數(shù)據(jù)庫操作工具 pydbclib的使用簡介
這篇文章主要介紹了python通用數(shù)據(jù)庫操作工具 pydbclib的使用簡介，幫助大家更好的理解和使用python，感興趣的朋友可以了解下2020-12-12
使用sklearn之LabelEncoder將Label標(biāo)準(zhǔn)化的方法
今天小編就為大家分享一篇使用sklearn之LabelEncoder將Label標(biāo)準(zhǔn)化的方法，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07