欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python基于回溯法子集樹模板解決馬踏棋盤問題示例

 更新時(shí)間:2017年09月11日 11:26:58   作者:羅兵  
這篇文章主要介紹了Python基于回溯法子集樹模板解決馬踏棋盤問題,簡單描述了國際象棋馬踏棋盤問題,并結(jié)合實(shí)例形式分析了Python使用回溯法子集樹模板解決馬踏棋盤問題的具體步驟與相關(guān)操作注意事項(xiàng),需要的朋友可以參考下

本文實(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ù)耗資源最小的方式

    協(xié)程是 Python 中另外一種實(shí)現(xiàn)多任務(wù)的方式,只不過比線程更小,占用更小執(zhí)行單元(理解為需要的資源)。這篇文章主要介紹了協(xié)程Python 中實(shí)現(xiàn)多任務(wù)耗資源最小的方式,需要的朋友可以參考下
    2020-10-10
  • python3+requests接口自動(dòng)化session操作方法

    python3+requests接口自動(dòng)化session操作方法

    今天小編就為大家分享一篇python3+requests接口自動(dòng)化session操作方法,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-10-10
  • Python實(shí)現(xiàn)功能完整的個(gè)人員管理程序

    Python實(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庫進(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-openpyxl表格讀取寫入的案例詳解

    Python-openpyxl表格讀取寫入的案例詳解

    這篇文章主要介紹了Python-openpyxl表格讀取寫入的案例分析,本文通過實(shí)例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2020-11-11
  • 使用Python創(chuàng)建websocket服務(wù)端并給出不同客戶端的請求

    使用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 函數(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-10
  • 詳解django三種文件下載方式

    詳解django三種文件下載方式

    這篇文章主要介紹了詳解django三種文件下載方式,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2018-04-04
  • Django中模版的子目錄與include標(biāo)簽的使用方法

    Django中模版的子目錄與include標(biāo)簽的使用方法

    這篇文章主要介紹了Django中模版的子目錄與include標(biāo)簽的使用方法,有利于Python的Django框架的模版布局,需要的朋友可以參考下
    2015-07-07
  • python中對數(shù)據(jù)進(jìn)行各種排序的方法

    python中對數(shù)據(jù)進(jìn)行各種排序的方法

    這篇文章主要介紹了python中對數(shù)據(jù)進(jìn)行各種排序的方法,本文給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下
    2019-07-07

最新評(píng)論