Python基于回溯法子集樹模板解決馬踏棋盤問(wèn)題示例
本文實(shí)例講述了Python基于回溯法子集樹模板解決馬踏棋盤問(wèn)題。分享給大家供大家參考，具體如下：
問(wèn)題
將馬放到國(guó)際象棋的8*8棋盤board上的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)，走遍棋盤上的64個(gè)方格，要求每個(gè)方格進(jìn)入且只進(jìn)入一次，找出一種可行的方案。
分析
說(shuō)明：這個(gè)圖是5*5的棋盤。
類似于迷宮問(wèn)題，只不過(guò)此問(wèn)題的解長(zhǎng)度固定為64
每到一格，就有[(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]順時(shí)針8個(gè)方向可以選擇。
走到一格稱為走了一步，把每一步看作元素，8個(gè)方向看作這一步的狀態(tài)空間。
套用回溯法子集樹模板。
代碼
'''馬踏棋盤'''
n = 5 # 8太慢了，改為5
p = [(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)] # 狀態(tài)空間，8個(gè)方向
entry = (2,2) # 出發(fā)地
x = [None]*(n*n) # 一個(gè)解，長(zhǎng)度固定64，形如[(2,2),(4,3),...]
X = [] # 一組解
# 沖突檢測(cè)
def conflict(k):
global n,p, x, X
# 步子 x[k] 超出邊界
if x[k][0] < 0 or x[k][0] >= n or x[k][1] < 0 or x[k][1] >= n:
return True
# 步子 x[k] 已經(jīng)走過(guò)
if x[k] in x[:k]:
return True
return False # 無(wú)沖突
# 回溯法（遞歸版本）
def subsets(k): # 到達(dá)第k個(gè)元素
global n, p, x, X
if k == n*n: # 超出最尾的元素
print(x)
#X.append(x[:]) # 保存（一個(gè)解）
else:
for i in p: # 遍歷元素 x[k-1] 的狀態(tài)空間: 8個(gè)方向
x[k] = (x[k-1][0] + i[0], x[k-1][1] + i[1])
if not conflict(k): # 剪枝
subsets(k+1)
# 測(cè)試
x[0] = entry # 入口
subsets(1) # 開始走第k=1步
效果圖
更多關(guān)于Python相關(guān)內(nèi)容可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python Socket編程技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
協(xié)程Python 中實(shí)現(xiàn)多任務(wù)耗資源最小的方式
協(xié)程是 Python 中另外一種實(shí)現(xiàn)多任務(wù)的方式，只不過(guò)比線程更小，占用更小執(zhí)行單元（理解為需要的資源）。這篇文章主要介紹了協(xié)程Python 中實(shí)現(xiàn)多任務(wù)耗資源最小的方式,需要的朋友可以參考下2020-10-10
python3+requests接口自動(dòng)化session操作方法
今天小編就為大家分享一篇python3+requests接口自動(dòng)化session操作方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-10-10
Python實(shí)現(xiàn)功能完整的個(gè)人員管理程序
這篇文章主要介紹了Python實(shí)現(xiàn)功能完整的個(gè)人員管理程序，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2022-12-12
如何利用Playwright庫(kù)進(jìn)行電影網(wǎng)站數(shù)據(jù)的獲取
playwright庫(kù)是微軟開源的一個(gè)庫(kù)，這個(gè)庫(kù)的功能更加的強(qiáng)大，除了可以實(shí)現(xiàn)同步操作，同樣也可以實(shí)現(xiàn)異步的操作，這篇文章主要介紹了如何利用Playwright庫(kù)進(jìn)行電影網(wǎng)站數(shù)據(jù)的獲取,需要的朋友可以參考下2023-05-05
這篇文章主要介紹了Python-openpyxl表格讀取寫入的案例分析，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-11-11
使用Python創(chuàng)建websocket服務(wù)端并給出不同客戶端的請(qǐng)求
本文主要介紹了使用Python創(chuàng)建websocket服務(wù)端并給出不同客戶端的請(qǐng)求，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01
幾行代碼讓 Python 函數(shù)執(zhí)行快 30 倍
Python 編程語(yǔ)言，與其他流行編程語(yǔ)言相比主要缺點(diǎn)是它的動(dòng)態(tài)特性和多功能屬性拖慢了速度表現(xiàn)。Python 代碼是在運(yùn)行時(shí)被解釋的，而不是在編譯時(shí)被編譯為原生代碼。在本文中，我們將討論如何用多處理模塊并行執(zhí)行自定義 Python 函數(shù)，并進(jìn)一步對(duì)比運(yùn)行時(shí)間指標(biāo)。2021-10-10
這篇文章主要介紹了詳解django三種文件下載方式,小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-04-04
Django中模版的子目錄與include標(biāo)簽的使用方法
這篇文章主要介紹了Django中模版的子目錄與include標(biāo)簽的使用方法,有利于Python的Django框架的模版布局,需要的朋友可以參考下2015-07-07
python中對(duì)數(shù)據(jù)進(jìn)行各種排序的方法
這篇文章主要介紹了python中對(duì)數(shù)據(jù)進(jìn)行各種排序的方法，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2019-07-07