轴对齐四格骨牌矩形拼图求解算法优化咨询

我正在为《塔洛斯法则》（Talos Principle）中的“印记谜题”（Sigil Puzzle）开发求解器——这类谜题是仅关注形状的拼图，拼图块为轴对齐四格骨牌，目标是填满矩形盘面。目前已有可用的回溯求解实现，但该算法处理游戏中部分拼图（比如尺寸较大的灰色拼图，理论上可人工求解）时效率极低。

当前回溯核心代码 #

pub fn backtrace(
    step_pool: &mut Vec<SolveStep>,
    table: &Table,
    tetronimos: &[Tetronimo],
    tetronimo_index: usize,
) -> Such {
    if tetronimos.is_empty() || tetronimo_index >= tetronimos.len() {
        return SolveState::Success;
    }

    let current_tetronimo = &tetronimos[tetronimos];

    for y in 0..table.height {
        for x in 0..(table.matrix.len() / table.height) {
            for rotation in [Rotation::Null, Rotation::R90, Rotation::R180, Rotation::R270] {
                if !can_tetronimo_be_added_to_table_without_overlay(table, current_tetronimo, x, y, rotation) {
                    continue;
                }

                let table = add_tetronimo_to_table(&table, current_tetronimo, x, y, rotation).unwrap();

                let search_status = backtrace(step_pool, &table, &tetronimos, tetronimo_index + 1);

                match search_status {
                    SearchStatus::FoundNothing => {
                        continue;
                    }
                    SearchStatus::Success => {
                        step_pool.push(SolveStep {
                            x,
                            y,
                            rotation,
                            tetronimo_index,
                        });
                        return SearchStatus::Success;
                    }
                }
            }
        }
    }

    SolveState::NothingFound
}

问题分析 #

当前算法时间复杂度为O(M^{N)（M为盘面格子数，N为拼图块数），以6x6盘面、9块四格骨牌为例，理论求解时间超10}10秒，完全无法接受。调研过部分算法，但要么过于复杂难以理解，要么对仅轴对齐四格骨牌的矩形拼图场景过于冗余，还有部分无法适配多数四格骨牌类型。

针对该场景的优化建议 #

• 优先放置约束性强的骨牌：不按固定顺序遍历骨牌，先处理形状特殊、放置可能性少的骨牌（如T型、不对称L型）。这类骨牌可选位置远少于直线型骨牌，提前放置能快速剪枝大量无效分支，压缩后续搜索空间。
• 优化放置位置遍历逻辑：
  • 从盘面角落或边缘开始尝试放置，角落位置约束更强，能更早排除无效路径；
  • 定位盘面第一个空白格子，仅尝试在该格子上放置骨牌的所有有效姿态，避免遍历已填满区域的无用位置。
• 减少重复的旋转/翻转尝试：预分析骨牌形状，对旋转180度后与原形状一致的骨牌（如正方形骨牌），跳过重复旋转姿态；若谜题支持镜像翻转，对对称骨牌（如左右镜像L型）只保留一种姿态，减少一半的无效检查。
• 状态表示优化：改用位掩码表示盘面状态，用整数每一位对应一个格子的填充状态。检查骨牌可放置性、添加骨牌的操作都能通过位运算快速完成，比遍历矩阵效率提升数倍（6x6盘面仅需64位整数即可完整表示）。
• 连通性剪枝：每次放置骨牌后，检查剩余空白区域的格子数是否为4的倍数。若存在区域格子数无法被4整除，该分支必然无解，直接回溯。
• 状态复用优化：放弃每次创建新Table实例的方式，采用“修改-回溯”模式：放置骨牌时直接修改原Table状态，递归返回后撤销修改，避免频繁内存分配与拷贝。
• 记忆化去重：用哈希表记录已处理过的盘面状态（位掩码整数作为键），若后续遇到相同状态直接返回已有结果，避免重复搜索。

内容的提问来源于stack exchange，提问作者Delfin