构建 4×4 拉丁方格：为颜色与情绪生成无重复行列的组合矩阵-php教程-PHP中文网

构建 4×4 拉丁方格：为颜色与情绪生成无重复行列的组合矩阵

本文介绍如何用回溯算法生成一个 4×4 的拉丁方格（latin square），确保每行每列中颜色和情绪均不重复，适用于配对约束类布局问题。

本文介绍如何用回溯算法生成一个 4×4 的拉丁方格（latin square），确保每行每列中颜色和情绪均不重复，适用于配对约束类布局问题。

该问题本质是构造一个双约束拉丁方格（Graeco-Latin Square）：给定两个大小均为 $n=4$ 的集合（颜色、情绪），需将全部 $n^2=16$ 个唯一配对填入 $n \times n$ 网格，使得每一行和每一列中：

所有颜色互不相同；
所有情绪互不相同。

这等价于同时满足两个正交拉丁方——即颜色构成一个拉丁方，情绪也构成一个拉丁方，且二者正交（每对 (color, emotion) 恰好出现一次）。对于 $n=4$，这样的正交拉丁方组是存在的（事实上，所有 $n \neq 2,6$ 均存在，而 $n=4$ 有多个解）。

以下是一个完整、可运行的 PHP 教程实现，采用递归回溯 + 冲突检测策略：

✅ 核心思路

预生成所有配对：枚举 $colors × $emotions 得到 16 个 [color, emotion] 元组；
按顺序尝试填充网格：从左上角 (0,0) 开始，逐格尝试未使用过的配对；
冲突检测（关键）：在填入前检查目标行列是否已含相同 color 或 emotion；
回溯机制：若某位置无法填入合法配对，则撤销上一步，尝试其他选项。

? 关键函数详解

`noCollision($element, $row, $col, $grid)`

判断将配对 $element = [$color, $emotion] 放入第 $row 行、$col 列是否合法：

function noCollision($element, $row, $col, $grid) {
    // 检查行冲突：同一行不能重复 color 或 emotion
    $rowSet = [];
    foreach ($grid[$row] as $cell) {
        if (!empty($cell)) {
            $rowSet[$cell[0]] = true; // color
            $rowSet[$cell[1]] = true; // emotion
        }
    }
    if (isset($rowSet[$element[0]]) || isset($rowSet[$element[1]])) {
        return false;
    }

    // 检查列冲突
    $colSet = [];
    foreach ($grid as $r => $rowArr) {
        if (!empty($rowArr[$col])) {
            $colSet[$rowArr[$col][0]] = true; // color
            $colSet[$rowArr[$col][1]] = true; // emotion
        }
    }
    return !isset($colSet[$element[0]]) && !isset($colSet[$element[1]]);
}

⚠️ 注意：此处将 color 和 emotion 统一视为“符号”加入同一哈希集检测，因二者值域无交集（如 'gold' 与 'happy' 不同名），故不会误判。

`makeGrid($combs, &$grid, $idx, $total)`

标准回溯主逻辑：尝试将第 $idx 个配对填入第一个空位。

function makeGrid($combs, &$grid, $idx, $total) {
    if ($idx === $total) return true; // 全部填完，成功

    $n = count($grid);
    for ($i = 0; $i <h4><code>generateGrid($colors, $emotions, &$grid)</code></h4><p>初始化网格并启动回溯：</p><pre class="brush:php;toolbar:false;">function generateGrid($colors, $emotions, &$grid) {
    // 生成全部配对
    $combs = [];
    foreach ($colors as $c) {
        foreach ($emotions as $e) {
            $combs[] = [$c, $e];
        }
    }

    // 初始化 n×n 空网格
    $n = count($colors);
    $grid = array_fill(0, $n, array_fill(0, $n, []));

    // 启动回溯
    if (makeGrid($combs, $grid, 0, $n * $n)) {
        return true;
    }

    $grid = []; // 失败则重置
    return false;
}

▶️ 使用示例

$colors   = ['gold', 'silver', 'bronze', 'wood'];
$emotions = ['happy', 'sad', 'wow', 'angry'];

$grid = [];
if (generateGrid($colors, $emotions, $grid)) {
    // 格式化输出为关联数组：['color' => 'emotion']
    $result = [];
    foreach ($grid as $i => $row) {
        $result[$i] = [];
        foreach ($row as $pair) {
            if (!empty($pair)) {
                $result[$i][$pair[0]] = $pair[1];
            }
        }
    }
    print_r($result);
} else {
    echo "No valid grid found.\n";
}