python實(shí)現(xiàn)棋盤覆蓋問(wèn)題及可視化

更新時(shí)間：2021年03月12日 14:31:09 作者：Patrick_cyk

這篇文章主要給大家介紹了關(guān)于python實(shí)現(xiàn)棋盤覆蓋問(wèn)題及可視化的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

問(wèn)題介紹

棋盤覆蓋問(wèn)題，是一種編程問(wèn)題。

如何應(yīng)用分治法求解棋盤覆蓋問(wèn)題呢？分治的技巧在于如何劃分棋盤，使劃分后的子棋盤的大小相同，并且每個(gè)子棋盤均包含一個(gè)特殊方格，從而將原問(wèn)題分解為規(guī)模較小的棋盤覆蓋問(wèn)題。k>0時(shí)，可將2k×2k的棋盤劃分為4個(gè)2（k-1）×2（k-1）的子棋盤。這樣劃分后，由于原棋盤只有一個(gè)特殊方格，所以，這4個(gè)子棋盤中只有一個(gè)子棋盤包含該特殊方格，其余3個(gè)子棋盤中沒(méi)有特殊方格。為了將這3個(gè)沒(méi)有特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，以便采用遞歸方法求解，可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處，從而將原問(wèn)題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問(wèn)題。遞歸地使用這種劃分策略，直至將棋盤分割為1×1的子棋盤。

問(wèn)題解釋來(lái)源百度

原網(wǎng)頁(yè)

效果展示

k=1
k=1
k=2
k=2

代碼實(shí)現(xiàn)

借助numpy處理數(shù)據(jù)，plot實(shí)現(xiàn)可視化。

使用面向?qū)ο蟮姆椒ㄔO(shè)計(jì)了棋盤類。

一步步將棋盤分為小區(qū)塊，指導(dǎo)區(qū)塊的邊長(zhǎng)為1，退出遞歸。

import numpy as np
import matplotlib.pyplot as plt


class Board:
 def __init__(self, size, x, y):
  '''
  初始化棋盤

  :param size: 棋盤邊長(zhǎng)
  :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ū)塊邊長(zhǎng)
  :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("請(qǐng)輸入正整數(shù)K(棋盤大小2^2k,2^2k):\n"))
 loc_x = eval(input("請(qǐng)輸入特殊點(diǎn)橫坐標(biāo):\n"))
 loc_y = eval(input("請(qǐng)輸入特殊點(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)

GitHub鏈接