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