每日算法 — 使用java实现孔明锁：空间约束传播与三维几何互锁检测

引言

孔明锁（又称鲁班锁）是中国传统木工智力玩具，由若干木条通过凹凸结构相互咬合而成。拆解和组装孔明锁需要理解各部件之间的空间约束关系。本文用Java实现孔明锁的核心求解逻辑，讲解约束传播算法如何逐层缩减部件的可行位置，以及三维几何碰撞检测如何判断木条之间是否构成有效互锁结构。

问题建模

将孔明锁抽象为三维空间中的长方体木条集合。每根木条有以下属性：
– 尺寸：长、宽、高（以基本单元格为单位）
– 位置：(x, y, z) 三维坐标
– 方向：沿X/Y/Z轴之一放置
– 缺口：木条上被挖去的部分，用于与其他木条咬合

经典的六根孔明锁中，每根木条尺寸相同（如 3×1×1），中间带有特定的十字形或L形缺口。六根木条两两正交，沿三个坐标轴各有两根。

核心算法一：三维AABB碰撞检测

判断两根木条是否发生碰撞（非缺口处的实体部分重叠），是孔明锁组装验证的基础。

import java.util.*;

public class KongmingLockSolver {

    /**
     * 三维空间中的长方体木条
     */
    static class WoodenBar {
        int id;
        int x, y, z;      // 左下角坐标
        int w, h, d;      // 沿X/Y/Z轴的长度
        Set<Gap> gaps;    // 缺口集合

        WoodenBar(int id, int x, int y, int z, int w, int h, int d) {
            this.id = id;
            this.x = x; this.y = y; this.z = z;
            this.w = w; this.h = h; this.d = d;
            this.gaps = new HashSet<>();
        }

        /**
         * 添加缺口：缺口是木条上的空心区域
         */
        void addGap(int gx, int gy, int gz, int gw, int gh, int gd) {
            gaps.add(new Gap(gx, gy, gz, gw, gh, gd));
        }

        /**
         * 获取木条的实体区域（总区域减去缺口）
         */
        List<AABB> getSolidParts() {
            List<AABB> solids = new ArrayList<>();
            solids.add(new AABB(x, y, z, x + w, y + h, z + d));

            // 用缺口裁剪实体区域（简化处理：直接记录缺口位置）
            // 实际实现中可用三维差集算法
            return solids;
        }

        AABB getBoundingBox() {
            return new AABB(x, y, z, x + w, y + h, z + d);
        }
    }

    /**
     * 轴对齐包围盒（Axis-Aligned Bounding Box）
     */
    static class AABB {
        int minX, minY, minZ;
        int maxX, maxY, maxZ;

        AABB(int x1, int y1, int z1, int x2, int y2, int z2) {
            this.minX = x1; this.minY = y1; this.minZ = z1;
            this.maxX = x2; this.maxY = y2; this.maxZ = z2;
        }

        /**
         * 判断两个AABB是否相交（碰撞检测核心）
         */
        boolean intersects(AABB other) {
            return this.minX < other.maxX && this.maxX > other.minX &&
                   this.minY < other.maxY && this.maxY > other.minY &&
                   this.minZ < other.maxZ && this.maxZ > other.minZ;
        }

        /**
         * 计算相交区域
         */
        AABB intersection(AABB other) {
            int ix1 = Math.max(this.minX, other.minX);
            int iy1 = Math.max(this.minY, other.minY);
            int iz1 = Math.max(this.minZ, other.minZ);
            int ix2 = Math.min(this.maxX, other.maxX);
            int iy2 = Math.min(this.maxY, other.maxY);
            int iz2 = Math.min(this.maxZ, other.maxZ);

            if (ix1 >= ix2 || iy1 >= iy2 || iz1 >= iz2) {
                return null; // 不相交
            }
            return new AABB(ix1, iy1, iz1, ix2, iy2, iz2);
        }

        int volume() {
            return (maxX - minX) * (maxY - minY) * (maxZ - minZ);
        }
    }

    static class Gap {
        int x, y, z, w, h, d;
        Gap(int x, int y, int z, int w, int h, int d) {
            this.x = x; this.y = y; this.z = z;
            this.w = w; this.h = h; this.d = d;
        }
    }

核心算法二：约束传播与可行域缩减

孔明锁的组装本质上是一个约束满足问题（CSP）。每根木条的放置受到其他木条的限制，可以通过约束传播逐步缩减可行域。

    /**
     * 约束传播求解器
     * 维护每根木条的可能位置集合，通过约束不断缩减
     */
    static class ConstraintSolver {
        List<WoodenBar> bars;
        Map<Integer, List<Position>> domains; // 每根木条的可行位置域

        ConstraintSolver(List<WoodenBar> bars) {
            this.bars = bars;
            this.domains = new HashMap<>();
            initializeDomains();
        }

        /**
         * 初始化每根木条的所有可能位置
         * 对于标准六根锁，每根木条沿一个轴放置，位置受限
         */
        void initializeDomains() {
            for (WoodenBar bar : bars) {
                List<Position> possible = new ArrayList<>();
                // 在 5×5×5 的组装空间内枚举可能位置
                for (int x = -2; x <= 2; x++) {
                    for (int y = -2; y <= 2; y++) {
                        for (int z = -2; z <= 2; z++) {
                            if (isValidInitialPosition(bar, x, y, z)) {
                                possible.add(new Position(x, y, z));
                            }
                        }
                    }
                }
                domains.put(bar.id, possible);
            }
        }

        boolean isValidInitialPosition(WoodenBar bar, int x, int y, int z) {
            // 中心约束：木条中心必须接近原点
            int cx = x + bar.w / 2;
            int cy = y + bar.h / 2;
            int cz = z + bar.d / 2;
            return Math.abs(cx) <= 1 && Math.abs(cy) <= 1 && Math.abs(cz) <= 1;
        }

        /**
         * 约束传播：根据已固定的木条，移除其他木条不可行的位置
         */
        boolean propagateConstraints() {
            boolean changed = true;
            int iterations = 0;
            final int MAX_ITER = 1000;

            while (changed && iterations < MAX_ITER) {
                changed = false;
                iterations++;

                for (WoodenBar bar : bars) {
                    List<Position> domain = domains.get(bar.id);
                    Iterator<Position> it = domain.iterator();

                    while (it.hasNext()) {
                        Position pos = it.next();
                        bar.x = pos.x; bar.y = pos.y; bar.z = pos.z;

                        // 检查与所有已确定或部分确定的木条的约束
                        if (!satisfiesConstraints(bar)) {
                            it.remove();
                            changed = true;
                        }
                    }

                    if (domain.isEmpty()) {
                        return false; // 无可行解
                    }
                }
            }
            return true;
        }

        /**
         * 检查木条 bar 的当前位置是否满足与其他所有木条的约束
         */
        boolean satisfiesConstraints(WoodenBar bar) {
            for (WoodenBar other : bars) {
                if (other.id == bar.id) continue;

                AABB box1 = bar.getBoundingBox();
                AABB box2 = other.getBoundingBox();

                // 若AABB不相交，则无约束
                if (!box1.intersects(box2)) continue;

                // 若相交，检查是否为合法的互锁（通过缺口咬合）
                AABB overlap = box1.intersection(box2);
                if (overlap == null) continue;

                // 简化判断：重叠区域必须至少被一方的缺口覆盖
                if (!isCoveredByGap(bar, overlap) && !isCoveredByGap(other, overlap)) {
                    return false; // 实体部分非法重叠
                }
            }
            return true;
        }

        /**
         * 检查给定区域是否完全被某木条的缺口覆盖
         */
        boolean isCoveredByGap(WoodenBar bar, AABB region) {
            for (Gap gap : bar.gaps) {
                AABB gapBox = new AABB(
                    bar.x + gap.x, bar.y + gap.y, bar.z + gap.z,
                    bar.x + gap.x + gap.w, bar.y + gap.y + gap.h, bar.z + gap.z + gap.d
                );
                if (gapBox.intersects(region)) {
                    // 简化：只要有缺口覆盖部分重叠区域即认为合法
                    return true;
                }
            }
            return false;
        }
    }

    static class Position {
        int x, y, z;
        Position(int x, int y, int z) { this.x = x; this.y = y; this.z = z; }
    }

核心算法三：拆卸序列搜索

孔明锁的拆解顺序是唯一的（或有限几种）。通过分析每根木条当前是否”自由”（沿某一方向移动不再受其他木条阻挡），可以找到正确的拆卸序列。

    /**
     * 寻找孔明锁的拆卸序列
     * @return 按拆卸顺序排列的木条ID列表
     */
    public List<Integer> findDisassemblySequence(List<WoodenBar> assembledBars) {
        List<Integer> sequence = new ArrayList<>();
        Set<Integer> removed = new HashSet<>();
        List<WoodenBar> remaining = new ArrayList<>(assembledBars);

        while (!remaining.isEmpty()) {
            boolean found = false;

            for (WoodenBar bar : remaining) {
                if (removed.contains(bar.id)) continue;

                // 检查木条是否至少有一个自由移动方向
                int[][] directions = {{1,0,0}, {-1,0,0}, {0,1,0}, {0,-1,0}, {0,0,1}, {0,0,-1}};

                for (int[] dir : directions) {
                    if (canSlideOut(bar, remaining, removed, dir[0], dir[1], dir[2])) {
                        sequence.add(bar.id);
                        removed.add(bar.id);
                        remaining.remove(bar);
                        found = true;
                        break;
                    }
                }
                if (found) break;
            }

            if (!found) {
                throw new IllegalStateException("无法找到合法的拆卸顺序，锁结构可能有误");
            }
        }

        return sequence;
    }

    /**
     * 检查木条是否可以沿指定方向滑出
     */
    boolean canSlideOut(WoodenBar bar, List<WoodenBar> allBars, 
                         Set<Integer> removed, int dx, int dy, int dz) {
        // 模拟沿方向无限移动，检查是否与其他未拆除的木条发生碰撞
        for (int step = 1; step <= 10; step++) {
            AABB moved = new AABB(
                bar.x + dx * step, bar.y + dy * step, bar.z + dz * step,
                bar.x + bar.w + dx * step, bar.y + bar.h + dy * step, bar.z + bar.d + dz * step
            );

            for (WoodenBar other : allBars) {
                if (other.id == bar.id || removed.contains(other.id)) continue;

                AABB otherBox = other.getBoundingBox();
                // 忽略缺口处的碰撞（简化：只要实体部分不撞即可）
                if (moved.intersects(otherBox)) {
                    // 检查相交区域是否被缺口覆盖
                    AABB overlap = moved.intersection(otherBox);
                    if (overlap != null && overlap.volume() > 0) {
                        // 需要更精细的缺口覆盖判断
                        if (!isCoveredByGap(bar, overlap) && !isCoveredByGap(other, overlap)) {
                            return false; // 实体碰撞，无法滑出
                        }
                    }
                }
            }
        }
        return true;
    }

    boolean isCoveredByGap(WoodenBar bar, AABB region) {
        for (Gap gap : bar.gaps) {
            AABB gapBox = new AABB(
                bar.x + gap.x, bar.y + gap.y, bar.z + gap.z,
                bar.x + gap.x + gap.w, bar.y + gap.y + gap.h, bar.z + gap.z + gap.d
            );
            if (gapBox.intersects(region)) return true;
        }
        return false;
    }

复杂度分析

其中 N 为木条数量（通常6根），D 为单根木条的位置域大小。由于 N 很小，所有算法在毫秒级即可完成。

总结

孔明锁的求解过程完美诠释了约束满足问题的求解范式：先用AABB碰撞检测建立空间约束关系，再通过约束传播缩减每根木条的可行域，最后用贪心策略寻找拆卸序列。这种”几何建模 → 约束传播 → 序列搜索”的三层架构，不仅适用于传统智力玩具，也可以推广到机械装配验证、蛋白质折叠模拟等三维空间推理任务中。