python实现棋盘覆盖问题及可视化
作者:Patrick_cyk 时间:2021-04-17 02:10:29
问题介绍
棋盘覆盖问题,是一种编程问题。
如何应用分治法求解棋盘覆盖问题呢?分治的技巧在于如何划分棋盘,使划分后的子棋盘的大小相同,并且每个子棋盘均包含一个特殊方格,从而将原问题分解为规模较小的棋盘覆盖问题。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)
GitHub链接
总结
来源:https://blog.csdn.net/m0_52571898/article/details/114678213
标签:python,棋盘,覆盖
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Python处理命令行参数模块optpars用法实例分析
2021-07-20 05:27:36
详解python异步编程之asyncio(百万并发)
2022-05-09 04:44:12
Python 自动化修改word的案例
2021-11-08 21:18:16
![](https://img.aspxhome.com/file/2023/7/64357_0s.jpg)
PyGame贪吃蛇的实现代码示例
2021-04-27 12:09:33
![](https://img.aspxhome.com/file/2023/9/92489_0s.png)
python 递归调用返回None的问题及解决方法
2022-12-21 05:52:56
如何调用Oracle存储过程?
2009-11-15 20:13:00
Python实现的旋转数组功能算法示例
2021-09-11 20:49:46
Python实现将目录中TXT合并成一个大TXT文件的方法
2023-02-11 18:38:12
python实现Decorator模式实例代码
2022-05-10 06:04:56
python删除文件、清空目录的实现方法
2021-06-02 02:53:06
Design IT.(2),关于好设计
2008-09-08 12:44:00
python库pydantic的简易入门教程
2022-06-27 14:05:28
CTF中的PHP特性函数解析之上篇
2023-06-14 02:19:58
![](https://img.aspxhome.com/file/2023/8/55518_0s.jpg)
对Python实现简单的API接口实例讲解
2023-11-20 03:27:04
![](https://img.aspxhome.com/file/2023/3/90663_0s.jpg)
next在python中返回迭代器的实例方法
2022-10-28 12:35:41
keras做CNN的训练误差loss的下降操作
2023-09-03 07:41:07
SQL常用数据库操作命令使用方法
2007-08-22 13:24:00
交互设计实用指南系列(12)—避免出错
2010-04-12 13:02:00
![](https://img.aspxhome.com/file/UploadPic/20104/12/t1-50s.png)
ASP 相关文章或者相关产品
2011-03-30 11:12:00
深度剖析使用python抓取网页正文的源码
2022-09-29 15:53:39