满足连通性约束的随机6×6矩阵高效生成算法咨询

我手动在Python里定义了16个符合要求的6×6矩阵，具体代码如下：

matrices = {
    "Simulation 1": [
        [1, 1, 1, 1, 1, 2],
        [1, 1, 1, 1, 2, 2],
        [1, 1, 1, 2, 2, 2],
        [1, 1, 1, 2, 3, 2],
        [1, 1, 1, 1, 3, 3],
        [1, 1, 1, 1, 3, 3]
    ],
    
    "Simulation 2": [
        [1, 1, 2, 2, 2, 2],
        [1, 1, 1, 2, 2, 2],
        [1, 1, 2, 2, 2, 2],
        [1, 1, 1, 2, 2, 2],
        [1, 1, 1, 2, 2, 3],
        [1, 1, 1, 3, 3, 3]
    ],
    
    "Simulation 3": [
        [1, 1, 2, 2, 2, 2],
        [1, 1, 1, 2, 2, 2],
        [1, 1, 1, 2, 3, 3],
        [1, 1, 2, 2, 3, 3],
        [1, 1, 1, 3, 3, 3],
        [1, 1, 3, 3, 3, 3]
    ],
    
    "Simulation 4": [
        [1, 1, 1, 1, 2, 2],
        [1, 1, 1, 2, 2, 2],
        [3, 1, 3, 3, 3, 2],
        [3, 3, 3, 3, 3, 2],
        [3, 3, 3, 3, 3, 2],
        [3, 3, 3, 3, 3, 3]
    ],
    
    "Simulation 5": [
        [1, 1, 1, 2, 2, 2],
        [1, 1, 1, 2, 2, 2],
        [1, 1, 1, 1, 3, 2],
        [1, 3, 3, 3, 3, 3],
        [3, 3, 3, 3, 3, 3],
        [3, 3, 3, 3, 3, 3]
    ],
    
    "Simulation 6": [
        [1, 1, 1, 1, 1, 2],
        [1, 1, 1, 2, 2, 2],
        [1, 1, 1, 1, 2, 2],
        [1, 1, 1, 1, 2, 3],
        [1, 3, 3, 3, 3, 3],
        [1, 3, 3, 3, 3, 3]
    ],
    
    "Simulation 7": [
        [1, 1, 1, 1, 2, 2],
        [1, 1, 1, 1, 1, 2],
        [1, 1, 1, 2, 2, 2],
        [1, 1, 3, 2, 2, 3],
        [1, 1, 3, 3, 3, 3],
        [3, 3, 3, 3, 3, 3]
    ],
    
    "Simulation 8": [
        [1, 1, 2, 2, 2, 2],
        [2, 2, 2, 2, 2, 2],
        [2, 2, 2, 2, 2, 2],
        [2, 2, 2, 2, 3, 3],
        [2, 2, 3, 3, 3, 3],
        [2, 2, 2, 3, 3, 3]
    ],
    
    "Simulation 9": [
        [1, 1, 2, 2, 2, 2],
        [1, 1, 1, 2, 2, 2],
        [1, 1, 1, 1, 2, 2],
        [1, 1, 1, 1, 3, 2],
        [1, 1, 1, 1, 3, 3],
        [1, 1, 3, 3, 3, 3]
    ],
    
    "Simulation 10": [
        [1, 1, 1, 2, 2, 2],
        [1, 1, 2, 2, 2, 2],
        [1, 1, 2, 2, 2, 2],
        [1, 1, 2, 2, 2, 3],
        [1, 1, 1, 1, 3, 3],
        [1, 1, 1, 3, 3, 3]
    ],
    
    "Simulation 11": [
        [1, 1, 1, 2, 2, 2],
        [1, 1, 2, 2, 2, 2],
        [1, 1, 2, 2, 2, 3],
        [1, 1, 1, 2, 3, 3],
        [1, 1, 1, 3, 3, 3],
        [1, 1, 1, 3, 3, 3]
    ],
    
    "Simulation 12": [
        [1, 1, 1, 1, 2, 2],
        [1, 1, 1, 1, 2, 2],
        [1, 1, 1, 1, 2, 2],
        [3, 1, 1, 3, 3, 3],
        [3, 3, 3, 3, 3, 3],
        [3, 3, 3, 3, 3, 3]
    ],
    
    "Simulation 13": [
        [1, 1, 1, 2, 2, 2],
        [1, 1, 1, 1, 2, 2],
        [1, 1, 1, 2, 2, 2],
        [1, 1, 1, 3, 3, 3],
        [1, 3, 3, 3, 3, 3],
        [3, 3, 3, 3, 3, 3]
    ],
    
    "Simulation 14": [
        [1, 1, 1, 2, 2, 2],
        [1, 1, 1, 1, 1, 2],
        [1, 1, 1, 1, 1, 2],
        [1, 1, 1, 3, 3, 2],
        [1, 3, 3, 3, 3, 3],
        [1, 3, 3, 3, 3, 3]
    ],
    
    "Simulation 15": [
        [1, 1, 1, 2, 2, 2],
        [1, 2, 2, 2, 2, 2],
        [1, 1, 1, 2, 2, 2],
        [1, 1, 1, 1, 3, 3],
        [1, 1, 1, 3, 3, 3],
        [1, 1, 1, 3, 3, 3]
    ],
    
    "Simulation 16": [
        [1, 1, 3, 2, 2, 2],
        [1, 1, 3, 2, 3, 3],
        [1, 1, 3, 3, 3, 3],
        [1, 1, 3, 3, 3, 3],
        [1, 1, 3, 3, 3, 3],
        [1, 1, 3, 3, 3, 3]
    ]
}

这些矩阵可视化后会呈现出不同的红、蓝、绿区块分布，矩阵的位置索引规则如下：

positions = [
    [1,  2,  3,  4,  5,  6],
    [7,  8,  9,  10, 11, 12],
    [13, 14, 15, 16, 17, 18],
    [19, 20, 21, 22, 23, 24],
    [25, 26, 27, 28, 29, 30],
    [31, 32, 33, 34, 35, 36]
]

所有有效矩阵都满足以下核心约束：

• 数值1代表红色，2代表蓝色，3代表绿色
• 固定位置：左上角(位置1)始终是红色，右上角(位置6)始终是蓝色，右下角(位置36)始终是绿色
• 同色区块必须是连通的：任意同色节点都能通过上下左右相邻的同色节点到达彼此，中途不会经过其他颜色

举个无效矩阵的例子：红色节点1被蓝色区块隔开，无法不经过蓝色节点到达其他红色节点，违反了连通性约束。

我的核心问题是：有没有一种算法可以快速生成大量（比如100个）满足这些约束的随机有效矩阵？能不能用树或图结构来实现高效生成？

改进后的生成算法（含可视化） #

基于trincot的思路，我补充了可视化功能，下面是完整的Python代码，既能生成符合要求的随机矩阵，又能直观展示结果：

import random
import matplotlib.pyplot as plt
import numpy as np

def make_matrix(n):
    mat = [[0] * n for _ in range(n)]
    frontier = set()              
    
    def place(row, col, color):
        mat[row][col] = color
        frontier.discard((row, col, 1))
        frontier.discard((row, col, 2))
        frontier.discard((row, col, 3))
        for next_row, next_col in (row-1, col), (row+1, col), (row, col-1), (row, col+1): 
            if 0 <= next_row < n and 0 <= next_col < n and mat[next_row][next_col] == 0:
                frontier.add((next_row, next_col, color))
    
    place(0, 0, 1)
    place(0, n-1, 2)
    place(n-1, n-1, 3)
    
    while frontier:
        place(*random.choice(list(frontier)))
        
    return mat

def visualize_matrix(mat):
    n = len(mat)
    colors = np.zeros((n, n, 3))
    
    for i in range(n):
        for j in range(n):
            if mat[i][j] == 1:
                colors[i, j] = [1, 0, 0]  # 红色对应数值1
            elif mat[i][j] == 2:
                colors[i, j] = [0, 0, 1]  # 蓝色对应数值2
            elif mat[i][j] == 3:
                colors[i, j] = [0, 1, 0]  # 绿色对应数值3
    
    plt.figure(figsize=(5, 5))
    plt.imshow(colors)
    plt.grid(True, color='black', linewidth=0.5)
    plt.xticks(np.arange(-0.5, n, 1), [])
    plt.yticks(np.arange(-0.5, n, 1), [])
    plt.tick_params(length=0)
    
    for i in range(n):
        for j in range(n):
            plt.text(j, i, str(mat[i][j]), ha="center", va="center", color="white")
    
    plt.tight_layout()
    plt.show()

# 批量生成并可视化4个矩阵
plt.figure(figsize=(15, 10))
for i in range(4):
    plt.subplot(2, 2, i+1)
    mat = make_matrix(6)
    n = len(mat)
    
    colors = np.zeros((n, n, 3))
    for r in range(n):
        for c in range(n):
            if mat[r][c] == 1:
                colors[r, c] = [1, 0, 0]  # 红色
            elif mat[r][c] == 2:
                colors[r, c] = [0, 0, 1]  # 蓝色
            elif mat[r][c] == 3:
                colors[r, c] = [0, 1, 0]  # 绿色
    
    plt.imshow(colors)
    plt.grid(True, color='black', linewidth=0.5)
    plt.title(f"Matrix #{i+1}")
    plt.xticks([])
    plt.yticks([])
    
    for r in range(n):
        for c in range(n):
            plt.text(c, r, str(mat[r][c]), ha="center", va="center", color="white")

plt.tight_layout()
plt.show()

# 生成5个矩阵并分别打印+单独可视化
for i in range(5):
    print(f"Matrix #{i+1}:")
    mat = make_matrix(6)
    for row in mat:
        print(row)
    print()
    visualize_matrix(mat)

这个算法的核心思路是边界扩展法：

1. 先固定三个必须的起始点（红、蓝、绿的固定位置）
2. 维护一个"边界集合"，记录所有可被扩展的空白位置及其可归属的颜色（即与该空白位置相邻的已着色节点的颜色）
3. 每次随机从边界集合中选一个位置和对应的颜色进行着色，然后更新边界集合
4. 重复直到所有位置都被填满

这种方法能保证每个颜色的区块自始至终都是连通的，而且生成速度非常快，完全可以轻松生成上百个符合要求的随机矩阵。

备注：内容来源于stack exchange，提问作者stats_noob