python實現棋盤覆蓋問題及可視化

Posted on by

問題介紹

棋盤覆蓋問題，是一種編程問題。

如何應用分治法求解棋盤覆蓋問題呢？分治的技巧在於如何劃分棋盤，使劃分後的子棋盤的大小相同，並且每個子棋盤均包含一個特殊方格，從而將原問題分解為規模較小的棋盤覆蓋問題。k>0時，可將2k×2k的棋盤劃分為4個2（k-1）×2（k-1）的子棋盤。這樣劃分後，由於原棋盤隻有一個特殊方格，所以，這4個子棋盤中隻有一個子棋盤包含該特殊方格，其餘3個子棋盤中沒有特殊方格。為瞭將這3個沒有特殊方格的子棋盤轉化為特殊棋盤，以便采用遞歸方法求解，可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，從而將原問題轉化為4個較小規模的棋盤覆蓋問題。遞歸地使用這種劃分策略，直至將棋盤分割為1×1的子棋盤。

問題解釋來源 百度

原網頁

效果展示

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

代碼實現

借助numpy處理數據，plot實現可視化。

使用面向對象的方法設計瞭棋盤類。

一步步將棋盤分為小區塊，指導區塊的邊長為1，退出遞歸。

import numpy as np
import matplotlib.pyplot as plt


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

    :param size: 棋盤邊長
    :param x: 特殊點橫坐標
    :param y: 特殊點縱坐標
    '''
    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):
    '''
    可視化函數

    :return: None
    '''
    plt.imshow(self.board, cmap=plt.cm.gray)
    plt.colorbar()
    plt.show()

  def fill_block(self, x, y):
    '''
    填充點(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):
    '''
    遞歸函數填充棋盤或子棋盤（下文稱區塊)

    :param s_x: 區塊左上角x
    :param s_y: 區塊左上角y
    :param size: 區塊邊長
    :param c_x: 區塊特殊點坐標x
    :param c_y: 區塊特殊點坐標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)] # 代表四個子區塊
    for i in ls:
      if i != pos: # 如果不是原有特殊點所在區塊，則構造特殊點並填充
        x = center[0] + i[0]
        y = center[1] + i[1]
        self.fill_block(x, y)
    self.t += 1 # 標記號加一，標記下一骨牌
    for i in ls:
      if i != pos: # 如果不是原有特殊點所在區塊
        # 所構造特殊點位置(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: # 如果是原有特殊點所在區塊
        x1 = s_x + i[0] * (size / 2)
        y1 = s_y + i[1] * (size / 2)
        self.fill(x1, y1, size / 2, c_x, c_y)

主函數

if __name__ == '__main__':
  k = eval(input("請輸入正整數K(棋盤大小2^2k,2^2k):\n"))
  loc_x = eval(input("請輸入特殊點橫坐標:\n"))
  loc_y = eval(input("請輸入特殊點縱坐標:\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鏈接

總結

到此這篇關於python實現棋盤覆蓋問題及可視化的文章就介紹到這瞭,更多相關python棋盤覆蓋問題內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：