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文件與目錄操作技巧匯總》
希望本文所述對大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
協(xié)程Python 中實(shí)現(xiàn)多任務(wù)耗資源最小的方式
協(xié)程是 Python 中另外一種實(shí)現(xiàn)多任務(wù)的方式,只不過比線程更小,占用更小執(zhí)行單元(理解為需要的資源)。這篇文章主要介紹了協(xié)程Python 中實(shí)現(xiàn)多任務(wù)耗資源最小的方式,需要的朋友可以參考下2020-10-10python3+requests接口自動(dòng)化session操作方法
今天小編就為大家分享一篇python3+requests接口自動(dòng)化session操作方法,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2018-10-10Python實(shí)現(xiàn)功能完整的個(gè)人員管理程序
這篇文章主要介紹了Python實(shí)現(xiàn)功能完整的個(gè)人員管理程序,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2022-12-12如何利用Playwright庫進(jìn)行電影網(wǎng)站數(shù)據(jù)的獲取
playwright庫是微軟開源的一個(gè)庫,這個(gè)庫的功能更加的強(qiáng)大,除了可以實(shí)現(xiàn)同步操作,同樣也可以實(shí)現(xiàn)異步的操作,這篇文章主要介紹了如何利用Playwright庫進(jìn)行電影網(wǎng)站數(shù)據(jù)的獲取,需要的朋友可以參考下2023-05-05使用Python創(chuàng)建websocket服務(wù)端并給出不同客戶端的請求
本文主要介紹了使用Python創(chuàng)建websocket服務(wù)端并給出不同客戶端的請求,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01幾行代碼讓 Python 函數(shù)執(zhí)行快 30 倍
Python 編程語言,與其他流行編程語言相比主要缺點(diǎn)是它的動(dòng)態(tài)特性和多功能屬性拖慢了速度表現(xiàn)。Python 代碼是在運(yùn)行時(shí)被解釋的,而不是在編譯時(shí)被編譯為原生代碼。在本文中,我們將討論如何用多處理模塊并行執(zhí)行自定義 Python 函數(shù),并進(jìn)一步對比運(yùn)行時(shí)間指標(biāo)。2021-10-10Django中模版的子目錄與include標(biāo)簽的使用方法
這篇文章主要介紹了Django中模版的子目錄與include標(biāo)簽的使用方法,有利于Python的Django框架的模版布局,需要的朋友可以參考下2015-07-07python中對數(shù)據(jù)進(jìn)行各種排序的方法
這篇文章主要介紹了python中對數(shù)據(jù)進(jìn)行各種排序的方法,本文給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2019-07-07