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)
总结
到此这篇关于python实现棋盘覆盖问题及可视化的文章就介绍到这了,更多相关python棋盘覆盖问题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
python递归法解决棋盘分割问题
题目描述:将一个8*8的棋盘进行分割,将原棋盘分割下一个矩阵,同时确保剩下的棋盘也是矩阵: 再将剩下的棋盘继续进行如上分割,这样割(n-1)次,最后原棋盘被分割成n块矩形棋盘: 注意:每次分割只能沿着棋盘格子的边进行分割 原棋盘每个格子都有一个分值,一个矩形棋盘的总分,为所含各格分值之和: 其中,Xi为第i块矩形棋盘的总分 对给出的棋盘和n,使得矩形棋盘总分的均方差最小,并输出 分析思路: 程序代码: # -*- coding: utf-8 -*- """ Created o
-
python自带tkinter库实现棋盘覆盖图形界面
python实现棋盘覆盖图形界面,供大家参考,具体内容如下 一.解决方案和关键代码 工具: python tkinter库 问题描述: 在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何k≥0,有4^k种不同的特殊棋盘. 在棋盘覆盖问题中,要用下图中 4 中不同形态的 L 型骨牌覆盖一个给定的特殊棋牌上除特殊方格以外的所有方格,且任何 2 个 L 型骨牌不得重叠覆盖
-
python使用turtle绘制国际象棋棋盘
本文实例为大家分享了python使用turtle画国际象棋棋盘的具体代码,供大家参考,具体内容如下 使用的方法是每一个小格每一个小格的画 import turtle for i in range(8): #一共有八列 for j in range(8):#每一行有八个格 turtle.forward(37.5) if j % 2 == 0:#判断是否为第奇数个格(是否画黑色格) if i % 2 ==0:#判断是否为奇数行(调整画黑色正方形时小海龟的转向) turtle.begin_fill()
-
Python基于回溯法子集树模板解决马踏棋盘问题示例
本文实例讲述了Python基于回溯法子集树模板解决马踏棋盘问题.分享给大家供大家参考,具体如下: 问题 将马放到国际象棋的8*8棋盘board上的某个方格中,马按走棋规则进行移动,走遍棋盘上的64个方格,要求每个方格进入且只进入一次,找出一种可行的方案. 分析 说明:这个图是5*5的棋盘. 类似于迷宫问题,只不过此问题的解长度固定为64 每到一格,就有[(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]顺时针8个方向可以选择. 走到一
-
python微信跳一跳系列之色块轮廓定位棋盘
在前几篇博文中,我们分别采用颜色识别,模板匹配,像素遍历等方法实现了棋子和棋盘的定位,具体内容可以参见我的前面的文章内容,在这一篇中,我们来探索一种定位棋盘的新方法. 分析 经过观察,我们看到,无论什么情况下,棋盘和背景之间总是存在着非常明显的色彩对比,这当然是必须的,否则玩游戏的人都无法分辨棋子.棋盘.背景,这个游戏就不可能大火.显然,如果我们将每一幅画面进行色块分割,将彩色图转变为黑白二值图,就可以将背景和棋盘隔离出来,然后对黑白图中的白色轮廓进行分析,将其中位置最高(y值最小)的轮廓标记出
-
python图形工具turtle绘制国际象棋棋盘
本文实例为大家分享了python图形工具turtle绘制国际象棋棋盘的具体代码,供大家参考,具体内容如下 #编写程序绘制一个国际象棋的棋盘 import turtle turtle.speed(30) turtle.penup() off = True for y in range(-40, 30 + 1, 10): for x in range(-40, 30 + 1, 10): if off: turtle.goto(x, y) turtle.pendown() turtle.begin_f
-
Python3解决棋盘覆盖问题的方法示例
本文实例讲述了Python3解决棋盘覆盖问题的方法.分享给大家供大家参考,具体如下: 问题描述: 在2^k*2^k个方格组成的棋盘中,有一个方格被占用,用下图的4种L型骨牌覆盖所有棋盘上的其余所有方格,不能重叠. 代码如下: def chess(tr,tc,pr,pc,size): global mark global table mark+=1 count=mark if size==1: return half=size//2 if pr<tr+half and pc<tc+half: c
-
python输出国际象棋棋盘的实例分享
国际象棋是当今国际上最流行的智力体育运动项目.青年人下棋可以锻炼思维.增强记忆力和培养坚强的意志:中年人下棋可以享受美学:老年下棋可以很好的休息娱乐.国际象棋游戏有自己的规则,需要两个人将棋子落在棋盘上. 棋子落在棋盘上事件,在计算机看来,是一段程序,而这些程序又由一系列的指令组成.关心编程语言的使用趋势的人都知道,最近几年,国内最火的两种语言非 Python 与 Go 莫属,今天,我们就在计算机上用python开启一段输出国际象棋棋盘的编程之旅. 程序分析:用i控制行,j来控制列,根据i+j的
-
Python turtle绘画象棋棋盘
通过使用turtle绘画象棋棋盘,供大家参考,具体内容如下 # 绘制象棋棋盘 import turtle t = turtle.Pen() t.width(2) # 设置画笔粗细 t.speed(1) # 设置画笔移动速度 # 画竖线 t.penup() t.goto(-400, -400) for i in range(9): t.pendown() if i != 0 and i != 8: t.goto(-400+i*100, 0) t.penup() t.goto(-400+i*100,
-
python实现棋盘覆盖问题及可视化
问题介绍 棋盘覆盖问题,是一种编程问题. 如何应用分治法求解棋盘覆盖问题呢?分治的技巧在于如何划分棋盘,使划分后的子棋盘的大小相同,并且每个子棋盘均包含一个特殊方格,从而将原问题分解为规模较小的棋盘覆盖问题.k>0时,可将2k×2k的棋盘划分为4个2(k-1)×2(k-1)的子棋盘.这样划分后,由于原棋盘只有一个特殊方格,所以,这4个子棋盘中只有一个子棋盘包含该特殊方格,其余3个子棋盘中没有特殊方格.为了将这3个没有特殊方格的子棋盘转化为特殊棋盘,以便采用递归方法求解,可以用一个L型骨牌覆盖这3
-
JavaScript编写棋盘覆盖代码详解
一.前言 之前做了一个算法作业,叫做棋盘覆盖,本来需要用c语言来编写的,但是因为我的c语言是半桶水(哈哈),所以索性就把网上的c语言写法改成JavaScript写法,并且把它的覆盖效果显示出来 二.关键代码 <!DOCTYPE html> <html> <head><meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <titl
-
Java基于分治算法实现的棋盘覆盖问题示例
本文实例讲述了Java基于分治算法实现的棋盘覆盖问题.分享给大家供大家参考,具体如下: 在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格,如何覆盖.四个L型骨牌如下图: 棋盘中的特殊方格如图: 实现的基本原理是将2^k * 2^k的棋盘分成四块2^(k - 1) * 2^(k - 1)的子棋盘,特殊方格一定在其中的一个子棋盘中,如果特殊方格在某一个子棋盘中,继续递归处理这个子棋盘,直到这个子棋盘中只有一个方格为止如果特殊方格不
-
Python实现决策树并且使用Graphvize可视化的例子
一.什么是决策树(decision tree)--机器学习中的一个重要的分类算法 决策树是一个类似于数据流程图的树结构:其中,每个内部节点表示一个属性上的测试,每个分支代表一个属性输出,而每个树叶结点代表类或者类的分布,树的最顶层是根结点 根据天气情况决定出游与否的案例 二.决策树算法构建 2.1决策树的核心思路 特征选择:从训练数据的特征中选择一个特征作为当前节点的分裂标准(特征选择的标准不同产生了不同的特征决策树算法). 决策树生成:根据所选特征评估标准,从上至下递归地生成子节点,直到数据集
-
python代码实现TSNE降维数据可视化教程
TSNE降维 降维就是用2维或3维表示多维数据(彼此具有相关性的多个特征数据)的技术,利用降维算法,可以显式地表现数据.(t-SNE)t分布随机邻域嵌入 是一种用于探索高维数据的非线性降维算法.它将多维数据映射到适合于人类观察的两个或多个维度. python代码 km.py #k_mean算法 import pandas as pd import csv import pandas as pd import numpy as np #参数初始化 inputfile = 'x.xlsx' #销量及
-
Python实现决策树并且使用Graphviz可视化的例子
一.什么是决策树(decision tree)--机器学习中的一个重要的分类算法 决策树是一个类似于数据流程图的树结构:其中,每个内部节点表示一个属性上的测试,每个分支代表一个属性输出,而每个树叶结点代表类或者类的分布,树的最顶层是根结点 根据天气情况决定出游与否的案例 二.决策树算法构建 2.1决策树的核心思路 特征选择:从训练数据的特征中选择一个特征作为当前节点的分裂标准(特征选择的标准不同产生了不同的特征决策树算法). 决策树生成:根据所选特征评估标准,从上至下递归地生成子节点,直到数据集
-
如何使用Python处理HDF格式数据及可视化问题
原文链接:https://blog.csdn.net/Fairy_Nan/article/details/105914203 HDF也是一种自描述格式文件,主要用于存储和分发科学数据.气象领域中卫星数据经常使用此格式,比如MODIS,OMI,LIS/OTD等卫星产品.对HDF格式细节感兴趣的可以Google了解一下. 这一次呢还是以Python为主,来介绍如何处理HDF格式数据.Python中有不少库都可以用来处理HDF格式数据,比如h5py可以处理HDF5格式(pandas中 read_hdf
-
Python爬取股票信息，并可视化数据的示例
前言 截止2019年年底我国股票投资者数量为15975.24万户, 如此多的股民热衷于炒股,首先抛开炒股技术不说, 那么多股票数据是不是非常难找, 找到之后是不是看着密密麻麻的数据是不是头都大了? 今天带大家爬取雪球平台的股票数据, 并且实现数据可视化 先看下效果图 基本环境配置 python 3.6 pycharm requests csv time 目标地址 https://xueqiu.com/hq 爬虫代码 请求网页 import requests url = 'https://xueq