Python基于回溯法子集樹模板解決馬踏棋盤問題示例
本文實(shí)例講述了Python基于回溯法子集樹模板解決馬踏棋盤問題。分享給大家供大家參考，具體如下：
問題
將馬放到國際象棋的8*8棋盤board上的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)，走遍棋盤上的64個(gè)方格，要求每個(gè)方格進(jìn)入且只進(jìn)入一次，找出一種可行的方案。
分析
說明：這個(gè)圖是5*5的棋盤。
類似于迷宮問題，只不過此問題的解長度固定為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è)解，長度固定64，形如[(2,2),(4,3),...]
X = [] # 一組解
# 沖突檢測
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)走過
if x[k] in x[:k]:
return True
return False # 無沖突
# 回溯法（遞歸版本）
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)
# 測試
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)文章
在Python中不僅可以繪制折線圖、柱狀圖、散點(diǎn)圖等常規(guī)圖外，還支持繪制量場圖、頻譜圖、提琴圖、箱型圖等特殊圖。本文將主要介紹如何繪制流線圖，需要的朋友可以參考一下2021-12-12
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)超級(jí)瑪麗游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-03-03
Python數(shù)據(jù)類型最全知識(shí)總結(jié)
學(xué)習(xí)一門語言,往往都是從Hello World開始. 但是筆者認(rèn)為,在一個(gè)黑框框中輸出一個(gè)“你好，世界”并沒有什么了不起,要看透事物的本質(zhì),熟悉一門語言,就要了解其底層,就是我們常常說的基礎(chǔ),本篇從python中的數(shù)據(jù)類型開始,需要的朋友可以參考下2021-05-05
關(guān)于Python中對(duì)變量賦值過程的理解
在Python中對(duì)變量賦值過程的理解，有助于學(xué)習(xí)者對(duì)Python的變量和所指向的對(duì)象之間的指向關(guān)系深刻理解，避免編程中多個(gè)變量賦值后，對(duì)變量結(jié)果的不確定，,需要的朋友可以參考下2023-05-05
python中SSH遠(yuǎn)程登錄設(shè)備的實(shí)現(xiàn)方法
本文主要介紹了python中SSH遠(yuǎn)程登錄設(shè)備，python中支持SSH協(xié)議的模塊主要有Paramiko和netmiko兩種，本文主要介紹了netmiko模塊，具有一定的參考價(jià)值，感興趣的可以了解一下2022-04-04
Python的元組與列表類似，不同之處在于元組的元素不能修改,元組使用小括號(hào),列表使用方括號(hào),元組創(chuàng)建很簡單,只需要在括號(hào)中添加元素,并使用逗號(hào)隔開即可2014-03-03
這篇文章主要介紹了python 屬性與 @property 方法的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)python，感興趣的朋友可以了解下2020-09-09
python實(shí)現(xiàn)按關(guān)鍵字篩選日志文件
今天小編大家分享一篇python實(shí)現(xiàn)按關(guān)鍵字篩選日志文件方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-12-12
這篇文章主要介紹了Python實(shí)現(xiàn)彈球小游戲的方法，文中講解非常細(xì)致，代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-08-08
Python實(shí)現(xiàn)城市公交網(wǎng)絡(luò)分析與可視化
這篇文章主要介紹了通過Python爬取城市公交站點(diǎn)、線路及其經(jīng)緯度數(shù)據(jù)，并做可視化數(shù)據(jù)分析。文中的示例代碼講解詳細(xì)，感興趣的可以學(xué)習(xí)一下2021-12-12