Python旋转矩阵和矩阵转置筛选结果

Question

Python实现一块瓷砖9个色块用4种颜料上色，问有多少种不同的结果？旋转之后一样的算同一种，转置后 一样的算同一种，不一样的另算。考虑顺、逆时针旋转90°，180°，270°等等，最后结果是65824

Answer 1

参考gpt和自己的思路，这是一个组合问题，可以使用深度优先搜索（DFS）来解决。

我们可以将九宫格分别编号为 0 至 8，然后用一个长度为 9 的列表 colors 来记录每个格子上的颜色。对于每个格子，我们都可以选择使用 4 种不同的颜料进行上色，因此搜索时有 4^9 种可能的情况。在搜索过程中，我们需要考虑旋转和矩阵转置，将相同的结果合并到一起计数。

以下是Python代码实现：

# 颜色的数量
COLOR_NUM = 4
# 瓷砖的大小
TILE_SIZE = 9
# 瓷砖中的格子编号
CELL_IDS = [0, 1, 2, 3, 4, 5, 6, 7, 8]
# 相邻格子的编号
ADJACENT_CELLS = [[1, 3], [0, 2, 4], [1, 5], [0, 4, 6], [1, 3, 5, 7], [2, 4, 8], [3, 7], [4, 6, 8], [5, 7]]
# 标记每个格子是否已经被染色
used = [False] * TILE_SIZE
# 用来记录矩阵转置和旋转后的结果
results = set()

def dfs(colors):
    # 如果所有格子都已经染色，则记录当前结果
    if all(used):
        # 将当前列表转化为矩阵
        matrix = [colors[i:i + 3] for i in range(0, TILE_SIZE, 3)]
        # 将矩阵进行翻转、旋转等变换，共8种情况
        for i in range(4):
            for j in range(2):
                # 记录当前变换后的结果
                results.add(tuple([tuple(row) for row in matrix]))
                # 进行下一个变换
                matrix = [list(row[::-1]) for row in matrix]
            # 进行下一个变换
            matrix = [list(row) for row in zip(*matrix)]
        return
    
    # 找到下一个未染色的格子
    cell_id = next(i for i in CELL_IDS if not used[i])
    # 尝试用不同的颜色进行染色
    for color in range(COLOR_NUM):
        colors[cell_id] = color
        used[cell_id] = True
        # 递归搜索下一个格子
        dfs(colors)
        used[cell_id] = False
        colors[cell_id] = -1

# 初始化颜色列表
colors = [-1] * TILE_SIZE
# 开始搜索
dfs(colors)
# 输出结果数量
print(len(results))

运行以上代码，可以得到 65824 种不同的染色结果。