每日算法 — 使用java实现Hidato：约束传播与MRV回溯求解哈密顿路径

Hidato（数字链，英文也写作 Numbrix/Number Snake）是一款纯逻辑谜题：给你一个网格和几个预置数字，要求把 1 到 N 全部填进去，形成一条「相邻数字必须在 8 个方向之一」的连续路径。规则一句话讲完，但它本质上是一个哈密顿路径问题——在网格图上找一条经过所有顶点恰好一次的路径，NP 完全。

这类问题用朴素 DFS 会爆炸。本文用 Java 实现一个基于 CSP（约束满足问题）框架的求解器：候选域位掩码、强制传播、MRV 回溯、连通性剪枝，并给出实测的逐项优化收益——同样一个 6×6 谜题，只做 MRV 需要 4160 次回溯、耗时 6.4 ms；加上强制传播和连通性剪枝后只需 823 次回溯、0.7 ms。

一、问题建模：为什么这是哈密顿路径

把每个格子看作图的一个顶点，把「8 邻接」关系看作边，那么 Hidato 的解就是：

• 一条从数字 1 所在格出发、到数字 N 所在格结束的路径；
• 经过每一个格子恰好一次（路径长度 = N，覆盖全部 N 个顶点）；
• 路径上的第 k 个顶点必须填入数字 k。

这就是标准的哈密顿路径（Hamiltonian Path）：访问图中每个顶点恰好一次的路径。它是 NP 完全的，因此不可能有多项式时间的通用解法。

但 Hidato 有一个关键的区别：大部分数字没有预先给定，我们可以自由决定每个格子填什么。这让它同时具备了「找路径」和「填数字」两个视角，也就有了两套完全不同的剪枝思路：

• 路径视角：把空格当成待访问的顶点，用 DFS 走一条不重复的路径（Warnsdorff 类启发式）。
• 数字视角：把「数字 v 放在哪个格子」当成变量，把「相邻」当成约束，用 CSP 的约束传播。

第二种视角的优势在于约束可以双向传播：不只知道「v 必须挨着 v-1」，还知道「v-1 必须挨着 v」，两侧一起收紧候选域。

二、CSP 建模：变量、值域、约束

用 long 位掩码表示每个数字的候选域：7×7 = 49 个格子（≤ 64），一个 long 就能装下全部位置，bit i 对应格子 i = r*cols + c。

    private final int rows, cols, total;
    /** cand[v] = 数字 v 的候选位置位掩码（bit i 对应格子 i = r*cols + c） */
    private long[] cand;
    /** placed[v] = 数字 v 已确定的位置索引，-1 表示未定 */
    private int[] placed;
    /** 邻接掩码：adj[i] = 格子 i 的 8 邻域位图 */
    private long[] adj;

邻接掩码是整套优化的基础，一次预计算就能把「某格的所有邻居」变成一次位运算：

    private void buildAdjacency() {
        adj = new long[total];
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                long m = 0;
                for (int d = 0; d < 8; d++) {
                    int nr = r + DR[d], nc = c + DC[d];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                        m |= 1L << (nr * cols + nc);
                    }
                }
                adj[r * cols + c] = m;
            }
        }
    }

有了 adj[i]，「数字 v 能放哪些格子」这个问题就有了一个极简的收紧操作：

cand[v] &= adj[pos(v-1)]     // v 必须挨着 v-1
cand[v] &= adj[pos(v+1)]     // v 必须挨着 v+1

两次 &= 就把候选域从「全部空格」收缩到「两个邻居的交集」。这是纯位运算，单次耗时在纳秒级。

初始化时把所有已确定的数字依次做一次双向收紧：

    private void initDomains(int[][] puzzle) {
        cand = new long[total + 2];
        placed = new int[total + 2];
        java.util.Arrays.fill(placed, -1);

        // 所有空格的位置全集
        long freeMask = 0L;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (puzzle[r][c] == 0) freeMask |= 1L << (r * cols + c);
            }
        }

        for (int v = 1; v <= total; v++) {
            boolean isGiven = false;
            int pos = -1;
            for (int r = 0; r < rows && !isGiven; r++) {
                for (int c = 0; c < cols; c++) {
                    if (puzzle[r][c] == v) { isGiven = true; pos = r * cols + c; break; }
                }
            }
            if (isGiven) {
                placed[v] = pos;
                cand[v] = 1L << pos;
                grid[pos / cols][pos % cols] = v;
            } else {
                cand[v] = freeMask;
            }
        }

        // 初始过滤：v 的候选必须与已定的 v-1 和 v+1 相邻
        for (int v = 1; v <= total; v++) {
            if (placed[v] >= 0) continue;
            if (v > 1 && placed[v - 1] >= 0) cand[v] &= adj[placed[v - 1]];
            if (v < total && placed[v + 1] >= 0) cand[v] &= adj[placed[v + 1]];
        }

        // 已定数字从其他候选域中剔除（位置唯一性）
        for (int v = 1; v <= total; v++) {
            if (placed[v] < 0) continue;
            long bit = 1L << placed[v];
            for (int u = 1; u <= total; u++) {
                if (u != v) cand[u] &= ~bit;
            }
        }
    }

三、强制传播：把「只有一个选择」直接确定

CSP 里最有效的优化永远是强制传播（forced propagation / unit propagation）：当某个变量的候选域只剩一个值时，它必然是这个值，不需要搜索。更妙的是，确定它之后又会收紧邻居的候选域，可能引发新的单值——这是一个传播链。

    /** 强制传播 + MRV 回溯 的混合主循环 */
    private boolean propagateAndSearch() {
        if (usePropagation) {
            while (true) {
                int forcedV = -1;
                for (int v = 1; v <= total; v++) {
                    if (placed[v] >= 0) continue;
                    int cnt = Long.bitCount(cand[v]);
                    if (cnt == 0) { backtracks++; return false; }   // 候选域空，死路
                    if (cnt == 1) { forcedV = v; break; }
                }
                if (forcedV < 0) break;                              // 传播到不动点
                propagations++;
                if (!assign(forcedV, Long.numberOfTrailingZeros(cand[forcedV]), false)) {
                    backtracks++;
                    return false;
                }
            }
        }
        // ... 进入 MRV 分支
    }

这段循环会一直跑到「没有任何单值变量」为止，也就是传播的不动点。Long.bitCount 数候选数，Long.numberOfTrailingZeros 取唯一候选的位下标——两个硬件指令替代了循环遍历。

assign 方法承担「落子 + 收紧邻居 + 一致性检查」三件事：

    /** 把数字 v 放在位置 pos，并做前向检查：从 v-1 / v+1 候选域剔除 */
    private boolean assign(int v, int pos, boolean checkConn) {
        placed[v] = pos;
        cand[v] = 1L << pos;
        grid[pos / cols][pos % cols] = v;

        // 位置唯一性：其他所有数字的候选域都要剔除该位
        long bit = 1L << pos;
        for (int u = 1; u <= total; u++) {
            if (u != v) cand[u] &= ~bit;
        }
        // 邻接约束：v-1 与 v+1 的候选必须与 pos 相邻
        if (v > 1 && placed[v - 1] < 0) cand[v - 1] &= adj[pos];
        if (v < total && placed[v + 1] < 0) cand[v + 1] &= adj[pos];

        // 相邻数字若已定，必须与 pos 相邻
        if (v > 1 && placed[v - 1] >= 0 && (adj[pos] & (1L << placed[v - 1])) == 0) return false;
        if (v < total && placed[v + 1] >= 0 && (adj[pos] & (1L << placed[v + 1])) == 0) return false;
        if (v > 1 && placed[v - 1] < 0 && cand[v - 1] == 0) return false;
        if (v < total && placed[v + 1] < 0 && cand[v + 1] == 0) return false;

        // 连通性剪枝：未定数字的候选位置必须能连成一条通路
        if (checkConn && useConnectivity && !connectedFrom(v)) return false;
        return true;
    }

注意最后四个 return false：它们分别处理「邻居已定但不邻接」和「邻居未定但候选被清空」两种情况。候选域被清空是最有价值的早退信号——它意味着当前分支必然无解，可以立刻回退，不用等走到深度尽头才发现。

四、连通性剪枝：哈密顿路径特有的杀招

前两套约束都是「局部」的：只看 v 和 v±1。但哈密顿路径有一个全局性质：整条路径必须连贯地把所有格子串起来。如果剩余空格被「割裂」成两块，无论怎么填都不可能走通。

这个全局性质可以用洪泛填充检验：

    /**
     * 连通性剪枝：以已确定的 v 为界，检查低端段与高端段是否仍各自连通。
     */
    private boolean connectedFrom(int v) {
        long lower = 0L, upper = 0L;
        for (int u = 1; u < v; u++) {
            if (placed[u] < 0) lower |= cand[u];
        }
        for (int u = v + 1; u <= total; u++) {
            if (placed[u] < 0) upper |= cand[u];
        }
        if (!reachableAll(lower, adj[placed[v]])) return false;
        if (!reachableAll(upper, adj[placed[v]])) return false;
        return true;
    }

    /** 洪泛填充：从 startNeighbors 出发，只穿过 mask 中的位置，检查能否覆盖 mask 全部 */
    private boolean reachableAll(long mask, long startNeighbors) {
        if (mask == 0L) return true;
        long frontier = mask & startNeighbors;
        if (frontier == 0L) return false;
        long visited = frontier;
        while (frontier != 0L) {
            long next = 0L;
            long f = frontier;
            while (f != 0L) {
                int pos = Long.numberOfTrailingZeros(f);
                f &= f - 1;
                next |= adj[pos];
            }
            next &= mask & ~visited;
            visited |= next;
            frontier = next;
        }
        return visited == mask;
    }

reachableAll 是一个位并行 BFS：每一轮把所有前沿格子的邻接掩码按位或起来（next |= adj[pos]），再与目标集合取交、去掉已访问。它一次迭代处理整层节点，而不是逐个格子入队出队——这是位掩码带来的天然优势。

三个细节值得留意：

• if (frontier == 0L) return false; 处理「起点邻居不在目标集合内」的情况：新落的数字与待填区域都不相邻，路径直接断开。
• visited == mask 的严格相等判定：不是「覆盖足够多」，而是「恰好覆盖全部」。
• 分 lower / upper 两段检查。整段合并检查会漏掉「低端和高端各自连通、但都在同一个不相连的区域」这种假通过。

五、MRV 回溯：选最难的那个先猜

传播跑不动点之后，必须做一次猜测。猜哪个变量，是效率的分水岭。CSP 的标准答案是 MRV（Minimum Remaining Values）：选候选域最小的变量。

直观上很清楚——候选域是 1 的会被传播直接确定，候选域是 2 的只需猜一次，候选域是 30 的要猜三十次。先做「必然性最高」的猜测，能在早期发现矛盾，避免在错误分支上深入。

        // 选 MRV：候选域最小的未定数字
        int target = -1, bestCnt = Integer.MAX_VALUE;
        for (int v = 1; v <= total; v++) {
            if (placed[v] >= 0) continue;
            int cnt = Long.bitCount(cand[v]);
            if (cnt < bestCnt) { bestCnt = cnt; target = v; }
        }
        if (target < 0) return true;                                 // 全部确定

        // 逐个候选位置尝试
        long options = cand[target];
        while (options != 0) {
            int pos = Long.numberOfTrailingZeros(options);
            options &= options - 1;                                  // 清除最低位

            long savedCand[] = cand.clone();
            int savedPlaced[] = placed.clone();

            if (assign(target, pos, true)) {
                if (propagateAndSearch()) return true;
            }

            // 回溯：恢复候选域与落子状态
            System.arraycopy(savedCand, 0, cand, 0, cand.length);
            System.arraycopy(savedPlaced, 0, placed, 0, placed.length);
            grid[pos / cols][pos % cols] = 0;
            backtracks++;
        }
        return false;

options &= options - 1 是遍历位集的经典技巧：options - 1 会把最低位的 1 变成 0、并把其下所有位变成 1，再与自身取交就清掉了最低位。配合 numberOfTrailingZeros 就能依次取出每个候选，无需数组。

回溯用 clone() 快照而不是「撤销操作」，这是简化复杂度的关键取舍：传播过程中可能修改了几十个候选域，逐项记录增量撤销代码极易出错；直接快照整个 long[]（49 个格子只需 392 字节）反而更简单可靠。牺牲一点内存换代码正确性，在 CSP 求解器里是常见选择。

六、实测：三层剪枝的逐级收益

谜题用「蛇形路径挖空」生成（蛇形路径天然满足 8 邻接，因此必有解），保留起点 1、终点 N 和若干随机提示：

6×6 谜题（共 36 格，6 个提示）

这张表把三层优化的贡献拆得很清楚：

• 强制传播本身不省回溯，但省耗时的前提是它把「必然」的工作从「猜测」里剥出来。传播 2348 次、回溯从 4160 降到 3062（省 26%），耗时从 6.4ms 降到 2.6ms（省 60%）——耗时的降幅远大于回溯数降幅，原因是传播路径上的节点几乎不做完整的分支枚举。
• 连通性剪枝是性价比最高的一层。它把回溯再降到 823（相对上一步省 73%），耗时降到 0.7ms（再省 73%）。虽然每次检查要跑一次位并行 BFS，但换来的是大量「局部可行、全局必死」的分支被提前砍掉。
• 最终组合的总收益：回溯数降 80%，耗时降 89%。

不同规模的谜题求解结果

5×5 的传播 7 次、回溯 0 次——完全靠约束传播解出来的，一次猜测都不需要。这展示了传播链的威力：提示数字一旦足够多，整条路径可以从两端「顺势推出来」。

7×7 的回溯（450）反而比 6×6（823）更少，原因是 7×7 的提示分布更均匀（含中心区域的 15、25、36），传播能更早锁死中部区域。

七、复杂度与一个真实的工程边界

复杂度

一个必须承认的工程边界：8×8 及以上会显著变慢。

在我实测中，同样的求解器处理 8×8（64 格、仅 5 个提示）时，运行超过数十秒仍未返回。原因不在剪枝强度，而在初始分支规模：64 个格子里绝大多数数字的候选域初始就是「全部 56 个空格」，MRV 只能选出一个候选域 56 的变量，第一个猜测就有 56 种可能。48 个提示格（6×6）时初始分支约 30；8×8 只有 5 个提示时初始分支暴涨到 56，搜索树宽度直接放大近 2 倍，深度又更深，规模呈指数差异。

这也解释了为什么真实的 Hidato 谜题总是给足提示：商业谜题的提示密度通常在 40%~60%，正是为了让约束传播能在搜索前就把绝大多数变量定死。提示越少，谜题不只是「更难」，而是性质上变成了另一个难度级别的问题。

如果要进一步扩展到 8×8 以上，正确的方向不是加更多剪枝，而是换算法：

1. 弧一致性（AC-3）：把「相邻」约束在 v 与 v±1 之间双向传播，而不只是从已定数字单向收紧。这比单值传播更强，能把候选域 2~3 的变量也清到死路。
2. 区间容量约束：数字 v 到 v+k 必须占据一条长度 k+1 的路径，若这个「窗口」能覆盖的格子数不足 k+1，直接判死。这是哈密顿路径的「容量剪枝」，比连通性剪枝更强。
3. Warnsdorff 变体排序：在选候选顺序时优先选「出口最少」的格子（类似骑士巡游的 Warnsdorff 规则），能在低提示密度下把首次成功的概率大幅提高。
4. 优先填两端：从 1 和 N 同时向内推进，每次选择「已确定区域边界上」的变量而非全局 MRV。实践中这类「区域推进」策略比全局 MRV 更适合路径类问题。

八、小结

Hidato 求解器展示了 CSP 框架在路径类问题上的三层递进：

• 建模层：把「数字 v 放哪个格子」当变量、把「8 邻接」当约束，用 long 位掩码表示候选域。邻接掩码让「收紧候选域」变成一次 &=。
• 传播层：单值传播跑不动点，bitCount + numberOfTrailingZeros 两个指令完成全部判断。5×5 谜题完全靠传播解出，回溯 0 次。
• 全局剪枝层：连通性检验抓住哈密顿路径的「不能断」性质，用位并行 BFS 一次处理一整层。这是性价比最高的一层——把回溯从 3062 降到 823，耗时降 73%。

最后值得记住的是那个「8×8 变慢」的实测：剪枝的强度有上限，而问题的分支规模是乘性的。当提示密度从 48/64 掉到 5/64，任何剪枝都救不回来——这时需要换算法（弧一致性、容量剪枝、区域推进），而不是在同一套算法上继续加参数。