棋盘覆盖问题算法分析python

棋盘覆盖问题是指在一个大小为2^n * 2^n的棋盘上，恰好有一个方格是特殊的，现在要用L型骨牌覆盖整个棋盘，求覆盖方案。这个问题可以使用分治算法来解决，具体步骤如下：

1.将整个棋盘分成四个大小相等的子棋盘，其中特殊方格在其中一个子棋盘中。

2.对于不包含特殊方格的三个子棋盘，使用递归的方式继续进行分治。

3.对于包含特殊方格的那个子棋盘，将其分成四个子棋盘，其中特殊方格在其中一个子棋盘中，然后对于不包含特殊方格的三个子棋盘，使用递归的方式继续进行分治。

4.重复上述步骤，直到棋盘被完全覆盖。

下面是一个Python实现的例子：

def chessboard_cover(board, tr, tc, dr, dc, size):
    global tile
    if size == 1:
        return
    t = tile
    tile += 1
    s = size // 2
    # 1
    if dr < tr + s and dc < tc + s:
        chessboard_cover(board, tr, tc, dr, dc, s)
    else:
        board[tr + s - 1][tc + s - 1] = t
        chessboard_cover(board, tr, tc, tr + s - 1, tc + s - 1, s)
    # 2
    if dr < tr + s and dc >= tc + s:
        chessboard_cover(board, tr, tc + s, dr, dc, s)
    else:
        board[tr + s - 1][tc + s] = t
        chessboard_cover(board, tr, tc + s, tr + s - 1, tc + s, s)
    # 3
    if dr >= tr + s and dc < tc + s:
        chessboard_cover(board, tr + s, tc, dr, dc, s)
    else:
        board[tr + s][tc + s - 1] = t
        chessboard_cover(board, tr + s, tc, tr + s, tc + s - 1, s)
    # 4
    if dr >= tr + s and dc >= tc + s:
        chessboard_cover(board, tr + s, tc + s, dr, dc, s)
    else:
        board[tr + s][tc + s] = t
        chessboard_cover(board, tr + s, tc + s, tr + s, tc + s, s)

# 测试
size = 8
board = [[0 for j in range(size)] for i in range(size)]
tile = 1
chessboard_cover(board, 0, 0, 0, 1, size)
for i in range(size):
    for j in range(size):
        print(str(board[i][j]).center(4), end='')
    print()