python實(shí)現(xiàn)棋盤覆蓋問題及可視化
問題介紹
棋盤覆蓋問題,是一種編程問題。
如何應(yīng)用分治法求解棋盤覆蓋問題呢?分治的技巧在于如何劃分棋盤,使劃分后的子棋盤的大小相同,并且每個(gè)子棋盤均包含一個(gè)特殊方格,從而將原問題分解為規(guī)模較小的棋盤覆蓋問題。k>0時(shí),可將2k×2k的棋盤劃分為4個(gè)2(k-1)×2(k-1)的子棋盤。這樣劃分后,由于原棋盤只有一個(gè)特殊方格,所以,這4個(gè)子棋盤中只有一個(gè)子棋盤包含該特殊方格,其余3個(gè)子棋盤中沒有特殊方格。為了將這3個(gè)沒有特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤,以便采用遞歸方法求解,可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處,從而將原問題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種劃分策略,直至將棋盤分割為1×1的子棋盤。
問題解釋來源 百度
效果展示
k=1
k=2
代碼實(shí)現(xiàn)
借助numpy處理數(shù)據(jù),plot實(shí)現(xiàn)可視化。
使用面向?qū)ο蟮姆椒ㄔO(shè)計(jì)了棋盤類。
一步步將棋盤分為小區(qū)塊,指導(dǎo)區(qū)塊的邊長為1,退出遞歸。
import numpy as np import matplotlib.pyplot as plt class Board: def __init__(self, size, x, y): ''' 初始化棋盤 :param size: 棋盤邊長 :param x: 特殊點(diǎn)橫坐標(biāo) :param y: 特殊點(diǎn)縱坐標(biāo) ''' self.special_block = (x, y) self.board = np.zeros((size, size), dtype=int) self.board[x][y] = (size * size - 1) / 3 + 1 self.t = 1 self.size = size def visualize(self): ''' 可視化函數(shù) :return: None ''' plt.imshow(self.board, cmap=plt.cm.gray) plt.colorbar() plt.show() def fill_block(self, x, y): ''' 填充點(diǎn)(x, y) :param x: x :param y: y :return: None ''' if self.board[x][y] == 0: self.board[x][y] = self.t else: raise Exception def fill(self, s_x, s_y, size, c_x, c_y): ''' 遞歸函數(shù)填充棋盤或子棋盤(下文稱區(qū)塊) :param s_x: 區(qū)塊左上角x :param s_y: 區(qū)塊左上角y :param size: 區(qū)塊邊長 :param c_x: 區(qū)塊特殊點(diǎn)坐標(biāo)x :param c_y: 區(qū)塊特殊點(diǎn)坐標(biāo)x :return: None ''' if size == 1: return pos = (round((c_x - s_x + 1) / size), round((c_y - s_y + 1) / size)) center = (round(s_x + size / 2 - 1), round(s_y + size / 2 - 1)) ls = [(0, 0), (0, 1), (1, 0), (1, 1)] # 代表四個(gè)子區(qū)塊 for i in ls: if i != pos: # 如果不是原有特殊點(diǎn)所在區(qū)塊,則構(gòu)造特殊點(diǎn)并填充 x = center[0] + i[0] y = center[1] + i[1] self.fill_block(x, y) self.t += 1 # 標(biāo)記號(hào)加一,標(biāo)記下一骨牌 for i in ls: if i != pos: # 如果不是原有特殊點(diǎn)所在區(qū)塊 # 所構(gòu)造特殊點(diǎn)位置(x, y) x = center[0] + i[0] y = center[1] + i[1] x1 = s_x + i[0] * (size / 2) y1 = s_y + i[1] * (size / 2) self.fill(x1, y1, size / 2, x, y) else: # 如果是原有特殊點(diǎn)所在區(qū)塊 x1 = s_x + i[0] * (size / 2) y1 = s_y + i[1] * (size / 2) self.fill(x1, y1, size / 2, c_x, c_y)
主函數(shù)
if __name__ == '__main__': k = eval(input("請輸入正整數(shù)K(棋盤大小2^2k,2^2k):\n")) loc_x = eval(input("請輸入特殊點(diǎn)橫坐標(biāo):\n")) loc_y = eval(input("請輸入特殊點(diǎn)縱坐標(biāo):\n")) size = 2 ** (2 * k) b = Board(size, loc_x, loc_y) b.fill(0, 0, size, loc_x, loc_y) b.visualize() print(b.board)
總結(jié)
到此這篇關(guān)于python實(shí)現(xiàn)棋盤覆蓋問題及可視化的文章就介紹到這了,更多相關(guān)python棋盤覆蓋問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Python采集熱搜數(shù)據(jù)實(shí)現(xiàn)詳解
這篇文章主要為大家介紹了Python采集熱搜數(shù)據(jù)實(shí)現(xiàn)示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-05-05使用matlab 判斷兩個(gè)矩陣是否相等的實(shí)例
這篇文章主要介紹了使用matlab 判斷兩個(gè)矩陣是否相等的實(shí)例,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-05-05Python實(shí)現(xiàn)簡單的多任務(wù)mysql轉(zhuǎn)xml的方法
這篇文章主要介紹了Python實(shí)現(xiàn)簡單的多任務(wù)mysql轉(zhuǎn)xml的方法,結(jié)合實(shí)例形式分析了Python查詢mysql結(jié)果集轉(zhuǎn)xml格式數(shù)據(jù)輸出的相關(guān)操作技巧,需要的朋友可以參考下2017-02-02python基礎(chǔ)while循環(huán)及if判斷的實(shí)例講解
下面小編就為大家?guī)硪黄猵ython基礎(chǔ)while循環(huán)及if判斷的實(shí)例講解。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-08-08python tkinter實(shí)現(xiàn)屏保程序
這篇文章主要為大家詳細(xì)介紹了python tkinter實(shí)現(xiàn)屏保程序,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-07-07calendar在python3時(shí)間中常用函數(shù)舉例詳解
這篇文章主要介紹了calendar在python3時(shí)間中常用函數(shù)的相關(guān)文章,對此知識(shí)點(diǎn)有興趣的朋友們可以學(xué)習(xí)下。2020-11-11Pycharm中python調(diào)用另一個(gè)文件類或者函數(shù)
本文主要介紹了Pycharm中python調(diào)用另一個(gè)文件類或者函數(shù),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07