棋盘覆盖问题python存储结构

棋盘覆盖问题是指用不同形状的L形骨牌覆盖一个2^n * 2^n的棋盘，使得棋盘上每个格子恰好被覆盖一次。在Python中，可以使用二维数组作为棋盘的存储结构，用0表示未被覆盖的位置，用1表示已经被覆盖的位置。例如，创建一个8 * 8的棋盘：

board = [[0 for i in range(8)] for j in range(8)]

接下来，可以根据L形骨牌的形状定义一个数组，表示每个骨牌所覆盖的位置。例如，对于一种骨牌形状，可以定义如下数组：

shape = [(0, 0), (0, 1), (1, 0)]

表示该骨牌覆盖了棋盘上的3个位置，其中第一个元素表示该位置距离骨牌左上角的行数，第二个元素表示该位置距离骨牌左上角的列数。在进行覆盖时，可以遍历棋盘上的每个位置，如果该位置未被覆盖，则尝试使用某个骨牌进行覆盖，如果能够覆盖，则将该位置标记为已覆盖并继续遍历；如果不能覆盖，则换一种骨牌进行尝试，直到所有骨牌都试过一遍为止。具体实现可以参考下面的代码：

board = [[0 for i in range(8)] for j in range(8)]

# 定义L形骨牌形状
shapes = [
    [(0, 0), (0, 1), (1, 0)],
    [(0, 0), (0, 1), (1, 1)],
    [(0, 0), (1, 0), (1, 1)],
    [(0, 1), (1, 0), (1, 1)]
]

def cover(board, shape, r, c, size, label):
    # 尝试使用骨牌覆盖(r, c)位置
    for dr, dc in shape:
        nr, nc = r + dr, c + dc
        if nr >= size or nc >= size or board[nr][nc] != 0:
            return False
    # 能够覆盖，则将骨牌放在(r, c)位置，并标记为已覆盖
    for dr, dc in shape:
        nr, nc = r + dr, c + dc
        board[nr][nc] = label
    return True

def solve(board, shapes, r, c, size, label):
    # 尝试覆盖棋盘上的每个位置
    if size == 1:
        return
    half = size // 2
    for shape in shapes:
        for i in range(2):
            for j in range(2):
                if cover(board, shape, r + i * half, c + j * half, half, label):
                    label += 1
                    solve(board, shapes, r + i * half, c + j * half, half, label)
    return

# 测试代码
solve(board, shapes, 0, 0, 8, 1)
for row in board:
    print(row)

以上代码中，`cover`函数用于尝试使用某个骨牌覆盖指定位置，如果能够覆盖则返回True，否则返回False。`solve`函数用于遍历棋盘上的每个位置，尝试使用不同的骨牌进行覆盖，直到所有位置都被覆盖为止。最后输出每个位置上的标记值即可。