服务器之家

服务器之家 > 正文

python实现棋盘覆盖问题及可视化

时间:2021-09-22 00:08     来源/作者:Patrick_cyk

问题介绍

棋盘覆盖问题,是一种编程问题。

python实现棋盘覆盖问题及可视化

如何应用分治法求解棋盘覆盖问题呢?分治的技巧在于如何划分棋盘,使划分后的子棋盘的大小相同,并且每个子棋盘均包含一个特殊方格,从而将原问题分解为规模较小的棋盘覆盖问题。k>0时,可将2k×2k的棋盘划分为4个2(k-1)×2(k-1)的子棋盘。这样划分后,由于原棋盘只有一个特殊方格,所以,这4个子棋盘中只有一个子棋盘包含该特殊方格,其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘,以便采用递归方法求解,可以用一个l型骨牌覆盖这3个较小棋盘的会合处,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略,直至将棋盘分割为1×1的子棋盘。

问题解释来源 百度

原网页

效果展示

k=1
python实现棋盘覆盖问题及可视化
k=2
python实现棋盘覆盖问题及可视化

代码实现

借助numpy处理数据,plot实现可视化。

使用面向对象的方法设计了棋盘类。

一步步将棋盘分为小区块,指导区块的边长为1,退出递归。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
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)

主函数

?
1
2
3
4
5
6
7
8
9
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棋盘覆盖问题内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!

原文链接:https://blog.csdn.net/m0_52571898/article/details/114678213

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
返回顶部