Python3解決棋盤覆蓋問題的方法示例
更新時間：2017年12月07日 11:48:19 作者：littlethunder
這篇文章主要介紹了Python3解決棋盤覆蓋問題的方法,簡單描述了棋盤覆蓋問題的概念、原理及Python相關(guān)操作技巧,需要的朋友可以參考下
本文實例講述了Python3解決棋盤覆蓋問題的方法。分享給大家供大家參考，具體如下：
問題描述：
在2^k*2^k個方格組成的棋盤中，有一個方格被占用，用下圖的4種L型骨牌覆蓋所有棋盤上的其余所有方格，不能重疊。
代碼如下：
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是棋盤寬度，必須是2^k，本例中n=8，特殊格子在(2,2)位置，如下圖所示：
采用分治法每次把棋盤分成4份，如果特殊格子在這個小棋盤中則繼續(xù)分成4份，如果不在這個小棋盤中就把該小棋盤中靠近中央的那個格子置位，表示L型骨牌的1/3占據(jù)此處，每一次遞歸都會遍歷查詢4個小棋盤，三個不含有特殊格子的棋盤置位的3個格子正好在大棋盤中央構(gòu)成一個完整的L型骨牌，依次類推，找到全部覆蓋方法。運(yùn)行結(jié)果如下：
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》
希望本文所述對大家Python程序設(shè)計有所幫助。
相關(guān)文章
在本篇文章里小編給大家整理的是一篇關(guān)于python中Matplotlib繪制直線的實例代碼內(nèi)容，有興趣的朋友們可以跟著學(xué)習(xí)下。2021-07-07
這篇文章主要介紹了Python 內(nèi)置高階函數(shù)，文中要介紹的內(nèi)置高階函數(shù)有map()、reduce() 函數(shù)、reduce() 函數(shù)、sorted() 函數(shù),需要的朋友可以參考一下文章的詳細(xì)內(nèi)容2021-11-11
解決python使用pd.read_csv()出現(xiàn)錯誤UnicodeDecodeError:?'utf-8&
你是否有過之前用pd.read打開csv文件都正常,但突然有一天運(yùn)行以前的代碼就突然報錯,這篇文章主要給大家介紹了關(guān)于如何解決python使用pd.read_csv()出現(xiàn)錯誤UnicodeDecodeError:?'utf-8'?codec?can't?decode......的相關(guān)資料,需要的朋友可以參考下2023-12-12
本文主要是針對Python的字典dict遍歷的4種方法進(jìn)行了性能測試，以便分析得出效率最高的一種方法2014-06-06
這篇文章主要介紹了python函數(shù)式編程實例,使用一個例子來闡述python函數(shù)式編程,需要的朋友可以參考下2014-06-06
這篇文章主要介紹了Python 中將值附加到集合的操作方法,通過使用 add() 方法或 update() 方法，你可以向 Python 中的集合中添加元素，在添加元素時，需要注意不允許重復(fù)元素和集合是無序的，本文通過示例代碼給大家介紹的非常詳細(xì)，需要的朋友可以參考下2023-05-05
pycharm 解除默認(rèn)unittest模式的方法
今天小編就為大家分享一篇pycharm 解除默認(rèn)unittest模式的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-11-11
Python實現(xiàn)的列表排序、反轉(zhuǎn)操作示例
這篇文章主要介紹了Python實現(xiàn)的列表排序、反轉(zhuǎn)操作,結(jié)合實例形式分析了Python針對列表的sort排序、以及基于reverse、切片的反轉(zhuǎn)操作相關(guān)實現(xiàn)技巧,需要的朋友可以參考下2019-03-03
Python3.6基于正則實現(xiàn)的計算器示例【無優(yōu)化簡單注釋版】
這篇文章主要介紹了Python3.6基于正則實現(xiàn)的計算器,涉及Python基于正則表達(dá)式的算術(shù)式遍歷、查找及數(shù)學(xué)運(yùn)算相關(guān)操作技巧,需要的朋友可以參考下2018-06-06
這篇文章主要介紹了用Python作圖的一個簡單實例，通過turtle模塊實現(xiàn)作圖，具有一定參考價值，需要的朋友可以了解下希望能給你帶來幫助2021-08-08