Python3解決棋盤(pán)覆蓋問(wèn)題的方法示例
本文實(shí)例講述了Python3解決棋盤(pán)覆蓋問(wèn)題的方法。分享給大家供大家參考，具體如下：
問(wèn)題描述：
在2^k*2^k個(gè)方格組成的棋盤(pán)中，有一個(gè)方格被占用，用下圖的4種L型骨牌覆蓋所有棋盤(pán)上的其余所有方格，不能重疊。
代碼如下：
def chess(tr,tc,pr,pc,size):
global mark
global table
mark+=1
count=mark
if size==1:
return
half=size//2
if pr<tr+half and pc<tc+half:
chess(tr,tc,pr,pc,half)
else:
table[tr+half-1][tc+half-1]=count
chess(tr,tc,tr+half-1,tc+half-1,half)
if pr<tr+half and pc>=tc+half:
chess(tr,tc+half,pr,pc,half)
else:
table[tr+half-1][tc+half]=count
chess(tr,tc+half,tr+half-1,tc+half,half)
if pr>=tr+half and pc<tc+half:
chess(tr+half,tc,pr,pc,half)
else:
table[tr+half][tc+half-1]=count
chess(tr+half,tc,tr+half,tc+half-1,half)
if pr>=tr+half and pc>=tc+half:
chess(tr+half,tc+half,pr,pc,half)
else:
table[tr+half][tc+half]=count
chess(tr+half,tc+half,tr+half,tc+half,half)
def show(table):
n=len(table)
for i in range(n):
for j in range(n):
print(table[i][j],end=' ')
print('')
mark=0
n=8
table=[[-1 for x in range(n)] for y in range(n)]
chess(0,0,2,2,n)
show(table)
n是棋盤(pán)寬度，必須是2^k，本例中n=8，特殊格子在(2,2)位置，如下圖所示：
采用分治法每次把棋盤(pán)分成4份，如果特殊格子在這個(gè)小棋盤(pán)中則繼續(xù)分成4份，如果不在這個(gè)小棋盤(pán)中就把該小棋盤(pán)中靠近中央的那個(gè)格子置位，表示L型骨牌的1/3占據(jù)此處，每一次遞歸都會(huì)遍歷查詢(xún)4個(gè)小棋盤(pán)，三個(gè)不含有特殊格子的棋盤(pán)置位的3個(gè)格子正好在大棋盤(pán)中央構(gòu)成一個(gè)完整的L型骨牌，依次類(lèi)推，找到全部覆蓋方法。運(yùn)行結(jié)果如下：
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門(mén)與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
- python自帶tkinter庫(kù)實(shí)現(xiàn)棋盤(pán)覆蓋圖形界面
- python使用turtle繪制國(guó)際象棋棋盤(pán)
- python圖形工具turtle繪制國(guó)際象棋棋盤(pán)
- Python基于回溯法子集樹(shù)模板解決馬踏棋盤(pán)問(wèn)題示例
- python微信跳一跳系列之色塊輪廓定位棋盤(pán)
- Python turtle繪畫(huà)象棋棋盤(pán)
- python輸出國(guó)際象棋棋盤(pán)的實(shí)例分享
- python遞歸法解決棋盤(pán)分割問(wèn)題
- python實(shí)現(xiàn)棋盤(pán)覆蓋問(wèn)題及可視化
相關(guān)文章
python機(jī)器學(xué)習(xí)實(shí)現(xiàn)決策樹(shù)
這篇文章主要為大家詳細(xì)介紹了python機(jī)器學(xué)習(xí)實(shí)現(xiàn)決策樹(shù)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-11-11
Python實(shí)現(xiàn)打印九九乘法表的不同方法總結(jié)
這篇文章主要為大家介紹了Python實(shí)現(xiàn)打印九九乘法表的幾種不同方法，文中的示例代碼講解詳細(xì)，簡(jiǎn)潔易懂，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2022-11-11
這篇文章主要介紹了Python函數(shù)裝飾器原理與用法,結(jié)合實(shí)例形式詳細(xì)分析了Python裝飾器的原理、功能、分類(lèi)、常見(jiàn)操作技巧與使用注意事項(xiàng),需要的朋友可以參考下2019-08-08
這篇文章主要介紹了詳解Python爬蟲(chóng)的基本寫(xiě)法 的相關(guān)資料,需要的朋友可以參考下2016-01-01
python標(biāo)準(zhǔn)算法實(shí)現(xiàn)數(shù)組全排列的方法
這篇文章主要介紹了python標(biāo)準(zhǔn)算法實(shí)現(xiàn)數(shù)組全排列的方法,實(shí)例分析了全排列的原理與Python實(shí)現(xiàn)技巧,需要的朋友可以參考下2015-03-03
Python基于matplotlib畫(huà)箱體圖檢驗(yàn)異常值操作示例【附xls數(shù)據(jù)文件下載】
這篇文章主要介紹了Python基于matplotlib畫(huà)箱體圖檢驗(yàn)異常值操作,涉及Python針對(duì)xls格式數(shù)據(jù)文件的讀取、matplotlib圖形繪制等相關(guān)操作技巧,并附帶xls數(shù)據(jù)文件供讀者下載參考,需要的朋友可以參考下2019-01-01
python 環(huán)境安裝及編輯器配置方法小結(jié)
這篇文章主要介紹了python 環(huán)境安裝及編輯器配置方法小結(jié)的相關(guān)資料,需要的朋友可以參考下2021-06-06
Python3開(kāi)發(fā)實(shí)例之非關(guān)系型圖數(shù)據(jù)庫(kù)Neo4j安裝方法及Python3連接操作Neo4j方法實(shí)例
這篇文章主要介紹了Python3開(kāi)發(fā)實(shí)例之非關(guān)系型圖數(shù)據(jù)庫(kù)Neo4j安裝方法及Python3連接操作Neo4j方法實(shí)例,需要的朋友可以參考下2020-03-03
使用TensorBoard進(jìn)行超參數(shù)優(yōu)化的實(shí)現(xiàn)
這篇文章主要介紹了使用TensorBoard進(jìn)行超參數(shù)優(yōu)化的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
這篇文章主要介紹了python常見(jiàn)模塊與用法,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)python的小伙伴們有一定的幫助,需要的朋友可以參考下2021-04-04