每日算法 — 使用java实现摩天楼数独：视线计数约束与位掩码回溯求解

一、从”看的见几栋楼”说起

摩天楼数独（Skyscrapers）的规则一句话能说完，却藏着比标准数独更紧的约束：

• 在一个 N×N 的网格里填入 1..N 的排列，保证每行、每列数字不重复（这一点和数独相同）。
• 网格四周的数字代表”从该方向看过去能看到几栋楼”。数字代表楼高，高的会挡住后面矮的。
• 求解即：给定四周的视线计数，还原整个网格。

例如一行是 [3,1,4,2]，从左往右看，能依次看到 3、4，共 2 栋（1 被 3 挡住、2 被 4 挡住）。这个”从左看 = 前缀最大值的变化次数”的性质，是本题全部算法的支点。

与数独相比，摩天楼数独有两个显著不同：

• 没有 3×3 宫约束，但多了 O(N) 条视线约束，而且每条约束都是”全局的”——它约束整行整列，而不是局部块。
• 约束是可提前判断的：视线计数是一个单调量，随着行内数字逐步填入，只增不减。这给了我们极强的剪枝能力，也让”尽早失败的搜索”成为最优策略。

本篇用 Java 实现一个完整的求解器，核心是：位掩码表示候选集、视线计数做增量校验、MRV（最少候选优先）启发式排序，以及一个”从两端同时收敛”的双向传播优化。

二、视线计数的数学性质

设一行填入序列为 a[0..N-1]。定义：

• 左视线数 L = 序列中”严格大于此前所有元素”的元素个数，即前缀最大值的更新次数。
• 右视线数 R = 从右往左看的同类计数。

三条性质可以直接用于剪枝：

性质 1（单调性）：如果该行只填了前 k 个格子，当前前缀最大值更新次数为 c。那么该行的最终视线数 L 满足 c <= L <= c + (N - k)。因为剩余每个格子最多贡献一次更新。

性质 2（端点必可见）：L >= 1 且 R >= 1，因为最靠近观察者的那栋楼一定可见。若 L = 1，则 a[0] = N（最高的楼必须放在最前面，否则后面的楼会被挡住）。这条推论极强，能直接确定端点值。

性质 3（互补约束）：L + R 的取值范围受 N 约束。当 L = N 时，该行必须是严格递增序列 [1,2,...,N]；当 R = N 时必为严格递减。这两种情况可以零搜索直接填充。

/**
 * 计算一行（或一列）的视线计数。
 * @param line 长度为 n 的数组，0 表示空格
 * @param fromLeft true 从左往右看，false 从右往左看
 */
public static int visibleCount(int[] line, boolean fromLeft) {
    int n = line.length;
    int max = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        int v = fromLeft ? line[i] : line[n - 1 - i];
        if (v == 0) break;             // 遇到空格，只能统计已知部分
        if (v > max) { max = v; cnt++; }
    }
    return cnt;
}

注意 v == 0 时 break 而不是 continue：视线是连续的，空格之后的内容对”已确定的可见数”没有贡献。

三、位掩码：候选集的内建表达

N×N 的每行需要填入 1..N 的排列。用位掩码 mask 表示”该行已用掉的数字”：

• 第 i 位（从 1 开始计数，即 1 << v）为 1 表示数字 v 已被使用。
• 剩余可选 = fullMask & ~usedMask，其中 fullMask = (1 << (N+1)) - 2（保留位 1..N）。

单元格 (r, c) 的候选集 = 行可用 ∩ 列可用：

/** 位掩码中 1 的个数 = 候选数，用于 MRV 排序 */
private static int popcount(int m) { return Integer.bitCount(m); }

/** 返回该格所有候选数字（1-based） */
private static int[] candidates(int rowMask, int colMask, int fullMask) {
    int free = fullMask & ~(rowMask | colMask);
    int cnt = Integer.bitCount(free);
    int[] res = new int[cnt];
    int k = 0;
    while (free != 0) {
        int v = Integer.numberOfTrailingZeros(free);
        res[k++] = v;
        free &= free - 1;
    }
    return res;
}

一位运算同时完成了”求交集”和”取候选列表”两件事。对比用 boolean[N+1] 数组做两次标记再求交，代码量减少一半，且没有对象分配。

四、数据结构设计

/**
 * 摩天楼数独求解器。
 * 约束来源分三类：行内不重复、列内不重复、四条边的视线计数。
 */
public class SkyscraperSolver {
    private final int n;
    private final int[][] grid;      // 0 表示空格
    private final int[] clueTop;     // 从上方看每一列的可见数
    private final int[] clueBottom;
    private final int[] clueLeft;    // 从左侧看每一行的可见数
    private final int[] clueRight;

    private final int[] rowMask;     // 每行已用数字掩码
    private final int[] colMask;     // 每列已用数字掩码
    private final int fullMask;

    private long nodes = 0;          // 搜索节点计数，用于性能分析
}

把行掩码和列掩码作为可变数组维护（落子时更新、回溯时还原），而不是每次从 grid 重新算——这是”增量维护”的核心。每次重算的代价是 O(N²)，而增量更新是 O(1)。

五、增量式可行性检查

搜索中最频繁的操作是”这个数字能不能放在这里”。它必须同时通过三重检查：

/**
 * 检查在 (r,c) 放入 v 后，是否仍然存在解的可能。
 * 三类检查按"最便宜优先"排序：行/列冲突 → 视线单调性 → 剩余格可填性。
 */
private boolean feasible(int r, int c, int v) {
    // 1) 行、列冲突（O(1)）
    if ((rowMask[r] & (1 << v)) != 0) return false;
    if ((colMask[c] & (1 << v)) != 0) return false;

    grid[r][c] = v;
    boolean ok = checkLine(r, true) && checkLine(c, false);
    if (ok) ok = checkRemaining(r, c);
    grid[r][c] = 0;
    return ok;
}

5.1 视线单调性检查

/**
 * 检查某一行/列的视线约束是否仍然可能满足。
 * 核心：已知部分的可见数不能超过线索，且加上剩余格子的最大可能增量后不能少于线索。
 */
private boolean checkLine(int idx, boolean isRow) {
    int[] line = extract(idx, isRow);
    int clueFromStart = isRow ? clueLeft[idx] : clueTop[idx];
    int clueFromEnd   = isRow ? clueRight[idx] : clueBottom[idx];

    // 已确定部分的可见数（从两端分别统计）
    int knownFromStart = visibleCount(line, true);
    int knownFromEnd   = visibleCount(line, false);
    int emptyCount = countZeros(line);

    // 性质 1：下界不能超过线索
    if (clueFromStart > 0 && knownFromStart > clueFromStart) return false;
    if (clueFromEnd   > 0 && knownFromEnd   > clueFromEnd)   return false;

    // 性质 1 上界：已知可见数 + 剩余格数 >= 线索
    if (clueFromStart > 0 && knownFromStart + emptyCount < clueFromStart) return false;
    if (clueFromEnd   > 0 && knownFromEnd   + emptyCount < clueFromEnd)   return false;

    return true;
}

这个检查是 O(N)。它把大量”填到一半才发现无解”的分支提前砍掉，是本题性能的主要来源。

5.2 剩余格可填性检查（Hall 型约束）

行/列掩码的另一个用途：剩余格子数必须等于剩余数字数。如果一行还剩 3 个空格，但只剩 2 个可用数字，立即失败。

/**
 * 检查该行/列剩余格子数与剩余可用数字数是否匹配。
 * 这是"排列约束"的必要条件，能捕获大量隐藏冲突。
 */
private boolean checkRemaining(int r, int c) {
    int rowEmpty = 0;
    for (int j = 0; j < n; j++) if (grid[r][j] == 0) rowEmpty++;
    if (n - Integer.bitCount(rowMask[r]) < rowEmpty) return false;

    int colEmpty = 0;
    for (int i = 0; i < n; i++) if (grid[i][c] == 0) colEmpty++;
    if (n - Integer.bitCount(colMask[c]) < colEmpty) return false;

    return true;
}

六、MRV 启发式：先填候选最少的格子

回溯搜索的效率几乎完全由”选哪个空格先填”决定。固定按行列顺序填是灾难性的：它会把最强的约束（候选唯一的格子）留到很晚才用上。

MRV（Minimum Remaining Values）策略：每次都选候选数最少的空格。

/**
 * 选择下一个要填充的格子，返回编码值 r*n+c；无空格返回 -1。
 * 若存在候选数为 0 的格子，直接返回它（触发快速失败）。
 */
private int selectCell() {
    int bestCell = -1, bestCount = Integer.MAX_VALUE;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] != 0) continue;
            int free = fullMask & ~(rowMask[r] | colMask[c]);
            int cnt = Integer.bitCount(free);
            if (cnt == 0) return r * n + c;      // 立即失败
            if (cnt < bestCount) { bestCount = cnt; bestCell = r * n + c; }
            if (cnt == 1) return bestCell;       // 唯一候选，最优选择
        }
    }
    return bestCell;
}

这里用 bestCell = -1 表示”所有格子已填满”，与”候选为0″的返回值区分开——调用方据 candidates 的数量决定是收尾还是失败。

七、主搜索循环

public boolean solve() {
    nodes++;
    int cell = selectCell();
    if (cell == -1) return true;            // 全部填满，解成立

    int r = cell / n, c = cell % n;
    int free = fullMask & ~(rowMask[r] | colMask[c]);

    // MRV 保证了这里 free 的位就是有序的候选，按从小到大尝试
    while (free != 0) {
        int v = Integer.numberOfTrailingZeros(free);
        free &= free - 1;

        if (!feasible(r, c, v)) continue;

        // 落子 + 增量更新
        grid[r][c] = v;
        rowMask[r] |= (1 << v);
        colMask[c] |= (1 << v);

        if (solve()) return true;

        // 回溯 + 精确还原
        grid[r][c] = 0;
        rowMask[r] ^= (1 << v);
        colMask[c] ^= (1 << v);
    }
    return false;
}

rowMask[r] ^= (1 << v) 能正确还原，前提是”落子前该位一定是 0″——这一点由 feasible 的冲突检查保证。用 ^= 而不是 &= ~ 是个小优化，在 JIT 后通常更快，但语义上必须确认前置条件，否则会静默产生错误。这类”依赖不变式的位运算”是位掩码代码最危险的地方，务必写注释。

八、双向收敛：全线索行的直接填充

性质 3 提供了一个跳过搜索的机会。当 clueLeft = N 或 clueRight = N 时，整行被唯一确定：

/**
 * 预填充：处理视线线索已达极值的行/列。
 * L == N → 严格递增 [1,2,...,N]
 * R == N → 严格递减 [N,...,2,1]
 */
private void presolve() {
    for (int i = 0; i < n; i++) {
        if (clueLeft[i] == n)  fillRow(i, true);
        if (clueRight[i] == n) fillRow(i, false);
        if (clueTop[i] == n)   fillCol(i, true);
        if (clueBottom[i] == n) fillCol(i, false);

        // 线索为 1 时，端点必为 N（性质 2）
        if (clueLeft[i] == 1)  place(i, 0, n);
        if (clueRight[i] == 1) place(i, n - 1, n);
        if (clueTop[i] == 1)   placeByCol(i, 0, n);
        if (clueBottom[i] == 1) placeByCol(i, n - 1, n);
    }
}

在多数题面中，这一步能确定 30%~50% 的格子。预填充的另一个好处是：它让 MRV 从第一轮就能看到更紧的候选集，搜索树规模呈数量级下降。

九、完整可运行项目

skyscraper/
├── pom.xml
└── src/main/java/com/example/skyscraper/
    ├── SkyscraperSolver.java   # 求解器核心
    ├── Puzzle.java             # 题面解析
    └── Main.java               # 端到端演示

<project xmlns="http://maven.apache.org/POM/4.0.0">
  <modelVersion>4.0.0</modelVersion>
  <groupId>com.example</groupId>
  <artifactId>skyscraper</artifactId>
  <version>1.0</version>
  <properties>
    <maven.compiler.source>17</maven.compiler.source>
    <maven.compiler.target>17</maven.compiler.target>
  </properties>
</project>

Main.java：

public class Main {
    public static void main(String[] args) {
        // 6x6 题面：线索 0 表示无约束
        int[] top    = {0, 3, 2, 2, 3, 0};
        int[] bottom = {0, 3, 2, 1, 2, 0};
        int[] left   = {0, 2, 3, 2, 1, 0};
        int[] right  = {0, 1, 2, 2, 3, 0};

        SkyscraperSolver solver = new SkyscraperSolver(6, top, bottom, left, right);
        long t0 = System.nanoTime();
        boolean ok = solver.solve();
        long ms = (System.nanoTime() - t0) / 1_000_000;

        System.out.println("solved = " + ok + ", " + ms + "ms, nodes = " + solver.nodes());
        if (ok) solver.printGrid();
    }
}

printGrid 输出应能通过边界线索自校验：对每一行重新计算 visibleCount，与 clueLeft/clueRight 比对。求解器必须自带这种自校验，否则算法有 bug 时会静默输出错误答案——这是逻辑谜题类题目最常见的失败模式。

十、复杂度分析与实测

时间复杂度上界是 O(N^(N²))（最坏情况全排列），但实际表现由剪枝决定。在一个 8×8、线索完整的题面上，实测数据：

这张表说明一个规律：每个剪枝手段的贡献是乘法级的，而且越靠后的优化乘数越大。从”固定顺序”到”MRV”，节点数下降两个数量级，而算法复杂度标签完全没变。这正是回溯类搜索的本质——它的实际性能不取决于大 O，而取决于”平均情况下多早失败”。

空间复杂度是 O(N²) 存储网格 + O(N) 深度递归栈，非常轻。

十一、可以继续做的优化

1. 候选数预计算表：对 N ≤ 5，可以预先枚举所有合法排列及其视线计数，做成 (clueLeft, clueRight) → 候选排列集合 的表。填一行时直接取表，而不是逐格搜索。这是”用空间换剪枝”的典型做法。
2. 行列联合传播：当某行只剩一个可行排列时立即代入，再触发列的新约束，形成 AC-3 式的约束传播闭环。这是把回溯搜索升级为约束传播求解器的关键一步。
3. 对称性破除：如果题面线索在转置下对称，可固定一个角的值，减少等价分支。这一步在竞赛类求解器里很常见，但需要严格证明对称性成立。

十二、小结

摩天楼数独的价值在于它把”约束满足”的三种核心技巧压缩在一个规则极简的题面里：

• 位掩码把候选集的表示与求交合并成常数时间操作；
• 单调性剪枝利用视线计数的”只增不减”，在填到一半时就能判定失败；
• MRV 启发式把最强的约束提前用上，让搜索树从”宽而深”变成”窄而深”。

一个值得带走的判断：当你面对一个约束满足问题时，先问的不是”用什么搜索算法”，而是”约束有没有单调量“。摩天楼的视线计数是单调的，所以它可以增量校验；数独的宫约束不是单调的（填一个数可能同时排除多个候选），所以它更依赖传播。识别出这个差别，比记住某个算法模板更有用。