Introduction to the issue
Board coverage issues, is a programming problem.
How to apply the partition method to solve the board covering problem? The skill of partitioning lies in how to divide the board so that the divided subboards are of the same size and each subboard contains a special square, thus decomposing the original problem into a smaller board coverage problem. k>0, the 2k × 2k board can be divided into four 2(k-1) × 2(k-1) subboards. After this division, since the original board has only one special square, only one of these 4 subboards contains that special square, and the remaining 3 subboards have no special square. In order to convert these 3 subboards without the special square into special boards for solving using a recursive approach, an L-shaped domino can be used to cover the meeting place of these 3 smaller boards, thus transforming the original problem into a 4 smaller scale board covering problem. This division strategy is used recursively until the board is partitioned into 1 × 1 subboards.
Explanation of the problem Source Baidu
original webpage
Effective demonstration
k=1
k=2
code implementation
Data is processed with the help of numpy and plot is visualized.
The Chessboard class was designed using an object-oriented approach.
Step by step, divide the board into small blocks, instruct the blocks to have a side length of 1, and exit the recursion.
import numpy as np
import as plt
class Board:
def __init__(self, size, x, y):
'''
Initializing the board
:param size: length of board sides
:param x: horizontal coordinates of special points
:param y: vertical coordinates of special points
'''
self.special_block = (x, y)
= ((size, size), dtype=int)
[x][y] = (size * size - 1) / 3 + 1
= 1
= size
def visualize(self):
'''
Visualization Functions
:return: None
'''
(, cmap=)
()
()
def fill_block(self, x, y):
'''
Fill points (x, y)
:param x: x
:param y: y
:return: None
'''
if [x][y] == 0:
[x][y] =
else:
raise Exception
def fill(self, s_x, s_y, size, c_x, c_y):
'''
Recursive function to fill a chessboard or subboard (hereafter referred to as a block)
:param s_x: upper left corner of the block x
:param s_y: upper left corner of the block y
:param size: length of the block's edge
:param c_x: Coordinates of the special point of the block x
:param c_y: Coordinate of the special point of the block 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)] # Represents four sub-blocks
for i in ls:
if i != pos: # If it is not the block where the original special point is located, the special point is constructed and populated
x = center[0] + i[0]
y = center[1] + i[1]
self.fill_block(x, y)
+= 1 # Marker plus one, mark the next domino #
for i in ls:
if i != pos: # If it's not the block where the original special point is located
# Position of constructed special point (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)
(x1, y1, size / 2, x, y)
else: # If it's the block where the original special point is located
x1 = s_x + i[0] * (size / 2)
y1 = s_y + i[1] * (size / 2)
(x1, y1, size / 2, c_x, c_y)
main function
if __name__ == '__main__':
k = eval(input("Please enter a positive integerK(Board size2^2k,2^2k):\n"))
loc_x = eval(input("Please enter the horizontal coordinates of the special point:\n"))
loc_y = eval(input("Please enter the vertical coordinates of the special point:\n"))
size = 2 ** (2 * k)
b = Board(size, loc_x, loc_y)
(0, 0, size, loc_x, loc_y)
()
print()
GitHub Link
summarize
to this article on the python implementation of the chessboard coverage problem and visualization of the article is introduced to this, more related python chessboard coverage problem content please search for my previous articles or continue to browse the following related articles I hope you will support me in the future more!