python棋盘覆盖问题 python实现棋盘覆盖问题及可视化
Patrick_cyk 人气:0想了解python实现棋盘覆盖问题及可视化的相关内容吗,Patrick_cyk在本文为您仔细讲解python棋盘覆盖问题的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:python编程,python围棋程序,python棋盘覆盖,下面大家一起来学习吧。
问题介绍
棋盘覆盖问题,是一种编程问题。
如何应用分治法求解棋盘覆盖问题呢?分治的技巧在于如何划分棋盘,使划分后的子棋盘的大小相同,并且每个子棋盘均包含一个特殊方格,从而将原问题分解为规模较小的棋盘覆盖问题。k>0时,可将2k×2k的棋盘划分为4个2(k-1)×2(k-1)的子棋盘。这样划分后,由于原棋盘只有一个特殊方格,所以,这4个子棋盘中只有一个子棋盘包含该特殊方格,其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘,以便采用递归方法求解,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略,直至将棋盘分割为1×1的子棋盘。
问题解释来源 百度
效果展示
k=1
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)
总结
加载全部内容