python实现棋盘覆盖问题及可视化
问题介绍
棋盘覆盖问题，是一种编程问题。
如何应用分治法求解棋盘覆盖问题呢？分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。k>0时，可将2k×2k的棋盘划分为4个2（k-1）×2（k-1）的子棋盘。这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。
问题解释来源百度
原网页
效果展示
k=2
代码实现
借助numpy处理数据，plot实现可视化。
使用面向对象的方法设计了棋盘类。
一步步将棋盘分为小区块，指导区块的边长为1，退出递归。
importnumpyasnp importmatplotlib.pyplotasplt classBoard: def__init__(self,size,x,y): ''' 初始化棋盘 :paramsize:棋盘边长 :paramx:特殊点横坐标 :paramy:特殊点纵坐标 ''' 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 defvisualize(self): ''' 可视化函数 :return:None ''' plt.imshow(self.board,cmap=plt.cm.gray) plt.colorbar() plt.show() deffill_block(self,x,y): ''' 填充点(x,y) :paramx:x :paramy:y :return:None ''' ifself.board[x][y]==0: self.board[x][y]=self.t else: raiseException deffill(self,s_x,s_y,size,c_x,c_y): ''' 递归函数填充棋盘或子棋盘（下文称区块) :params_x:区块左上角x :params_y:区块左上角y :paramsize:区块边长 :paramc_x:区块特殊点坐标x :paramc_y:区块特殊点坐标x :return:None ''' ifsize==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)]#代表四个子区块 foriinls: ifi!=pos:#如果不是原有特殊点所在区块，则构造特殊点并填充 x=center[0]+i[0] y=center[1]+i[1] self.fill_block(x,y) self.t+=1#标记号加一，标记下一骨牌 foriinls: ifi!=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棋盘覆盖问题内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。