每日算法 — 使用java实现数织：有限自动机建模与约束传播求解

一、数织的难点不在「填格子」，在「排除」

数织（Nonogram，日本叫「お絵かきロジック」，国内也叫「逻辑绘画谜题」「像素拼图」）的规则极端简单：

• 每一行的左侧写着一串数字，表示这一行中连续黑块的长度，按从左到右的顺序排列；
• 每一列的上方同理，从上到下；
• 数字之间至少隔一个空格。填完全部行列线索，就得到一张像素图。

一个 10×10 的谜题，线索如下：

行: [2,2] [7] [10] [8] [6] [4] [2] [2] [] []
列: [1] [3] [5] [6] [7] [7] [6] [5] [2] [1]

它的答案是一颗像素爱心。看起来简单，但搜索空间大得惊人：

• 各行候选排列数相乘 = 21 × 4 × 1 × 3 × 5 × 7 × 9 × 9 × 1 × 1 = 714,420
• 各列候选排列数相乘 = 10 × 8 × 6 × 5 × 4 × 4 × 5 × 6 × 9 × 10 = 103,680,000

纯暴力「按行枚举 + 逐列校验」的搜索量在 10⁸ 量级。而实际上这个谜题完全不需要回溯——纯约束传播 3 轮扫描就能解出。这就是本文要讲的：为什么数织的正确解法是「先建模成有限自动机，再做约束传播」。

二、单行就是一个 DFA

这个观察是数织求解的核心洞察：一行的所有合法填充方式，恰好是某个确定性有限自动机（DFA）接受的语言。

DFA 的状态可以定义为 (j, run)：

• j：当前正在处理第几个线索（0-based，j == K 表示所有线索都已完成）；
• run：当前这个黑块已经连续填了几个格子（0 表示还没开始这一块）。

转移规则：

接受条件是「读完整行后处于 (K, 0)」。这条规则自动保证了「数字之间至少隔一个空格」——因为闭合一个块之后必须先读一个 . 才能进入下一块。

把它写成 DP，就能在 O(n × K × maxClue) 的时间里完成两件事：

1. 计数：这一行有多少种合法排列（用于判断约束强弱）；
2. 枚举：这一行所有合法排列的完整列表（用于传播）。

对比一下暴力枚举的效率：对于 [2,2] 这样一行，DP 只需约 10 × 2 × 2 = 40 个状态转移，而暴力枚举要试 C(10,2) × C(8,2) 次。DP 的收益随行长和线索数增长而放大。

三、约束传播：把「候选集」收缩

有了每行的候选列表和每列的候选列表，剩下的事情就是标准的 AC-3 风格约束传播：

重复直到无变化：
  对每一行:
    过滤候选集 —— 只保留与当前网格已知值不冲突的候选
    若候选集为空 -> 矛盾，回溯
    对每个格子: 若所有候选在该格上取值相同 -> 该格确定
  对每一列: 同上

这里有两个关键点：

第一，过滤和定值是同一个循环。 不需要「先过滤所有，再统一赋值」——在过滤的同时就把「候选集中该格取值唯一」的格子定下来，下一轮传播会立刻用上这些新信息。这就是「原地传播」，收敛比批量更新快得多。

第二，「候选集全同」的判定必须按格独立。 一行有 21 个候选，不意味着 21 个格子都能定值；只有某个格子在所有候选里都是 #（或都是 .）时才能定值。这是传播的唯一信息来源。

对本文的爱心谜题，实测传播效果：

扫描 1 轮后：未知格子 22 个
扫描 2 轮后：未知格子 0 个   <- 完全解出，无需回溯
扫描 3 轮后：确认收敛（无变化）

两轮有效扫描就解决了一个 10×10 的谜题，耗时在毫秒级。这就是「建模正确」带来的红利：把 10⁸ 的搜索空间压缩成了 3 次线性扫描。

四、完整 Java 实现

4.1 线索与工具

import java.util.*;

/** 数织谜题：行列线索 + 网格状态 */
final class Nonogram {
    final int h, w;
    final int[][] rowClues, colClues;
    /** 网格：0 = 未知, 1 = 黑, -1 = 白 */
    final int[][] grid;

    Nonogram(int[][] rowClues, int[][] colClues) {
        this.h = rowClues.length;
        this.w = colClues.length;
        this.rowClues = rowClues;
        this.colClues = colClues;
        this.grid = new int[h][w];
    }

    /** 从一行字符还原线索，例如 "..##..##.." -> [2, 2] */
    static int[] cluesOf(String line) {
        List<Integer> out = new ArrayList<>();
        int cnt = 0;
        for (char ch : line.toCharArray()) {
            if (ch == '#') cnt++;
            else { if (cnt > 0) { out.add(cnt); cnt = 0; } }
        }
        if (cnt > 0) out.add(cnt);
        return out.stream().mapToInt(Integer::intValue).toArray();
    }
}

用 int 三态（0/1/-1）而不是 boolean，是为了表达「未知」——这是约束传播的必要条件。若用 boolean，就必须再配一个 boolean[] known，反而更啰嗦。

4.2 单行的 DFA + DP

/**
 * 单行求解器：把线索建模为 DFA，用记忆化 DP 判定可达性，再反向重建所有合法排列。
 * 状态 (i, j, run)：位置 i、当前线索下标 j、当前块已填长度 run。
 */
final class LineSolver {
    final int[] clues;
    final int n;              // 行长
    final int[][] memo;       // memo[i][j*(n+1)+run] = 0 未知 / 1 可行 / -1 不可行

    LineSolver(int[] clues, int n) {
        this.clues = clues;
        this.n = n;
        // run 的取值范围 0..n，j 的取值范围 0..K
        this.memo = new int[n + 1][(clues.length + 1) * (n + 1)];
    }

    /** 从状态 (i,j,run) 出发能否合法读完剩余格子 */
    boolean feasible(int i, int j, int run) {
        if (i == n) {
            // 接受条件：所有线索已完成，或最后一个块刚好收尾
            return j == clues.length || (j == clues.length - 1 && run == clues[j]);
        }
        int key = j * (n + 1) + run;
        if (memo[i][key] != 0) return memo[i][key] == 1;

        boolean ok = false;

        // 分支 1：填黑
        if (j < clues.length && run < clues[j] && feasible(i + 1, j, run + 1)) ok = true;

        // 分支 2：填白
        if (!ok && j < clues.length) {
            if (run == 0) {
                // 还没开始这一块：可以继续空着
                if (feasible(i + 1, j, 0)) ok = true;
            } else if (run == clues[j]) {
                // 这一块刚好长度够了：必须用白格收尾，并进入下一块
                if (feasible(i + 1, j + 1, 0)) ok = true;
            }
        } else if (!ok && j == clues.length) {
            // 所有块都完成了，剩下的必须全白
            ok = true;
        }

        memo[i][key] = ok ? 1 : -1;
        return ok;
    }

    /** 枚举所有合法排列，返回用 boolean[] 表示的列表（true = 黑） */
    List<boolean[]> allCandidates() {
        List<boolean[]> res = new ArrayList<>();
        boolean[] cur = new boolean[n];
        collect(0, 0, 0, cur, res);
        return res;
    }

    private void collect(int i, int j, int run, boolean[] cur, List<boolean[]> res) {
        if (i == n) {
            if (j == clues.length || (j == clues.length - 1 && run == clues[j]))
                res.add(cur.clone());
            return;
        }
        if (!feasible(i, j, run)) return;

        if (j == clues.length) {              // 剩余全白，直接批量填充
            for (int k = i; k < n; k++) cur[k] = false;
            res.add(cur.clone());
            return;
        }

        // 先试黑（剪枝更早生效）
        if (run < clues[j] && feasible(i + 1, j, run + 1)) {
            cur[i] = true;
            collect(i + 1, j, run + 1, cur, res);
            cur[i] = false;
        }

        // 再试白
        if (run == 0) {
            if (feasible(i + 1, j, 0)) collect(i + 1, j, 0, cur, res);
        } else if (run == clues[j]) {
            if (feasible(i + 1, j + 1, 0)) collect(i + 1, j + 1, 0, cur, res);
        }
    }

    /** 候选排列总数（用于评估约束强度，不需真的枚举） */
    long count() {
        return countFrom(0, 0, 0);
    }

    private long countFrom(int i, int j, int run) {
        if (i == n) return (j == clues.length || (j == clues.length - 1 && run == clues[j])) ? 1 : 0;
        if (j == clues.length) return 1;
        long t = 0;
        if (run < clues[j]) t += countFrom(i + 1, j, run + 1);
        if (run == 0) t += countFrom(i + 1, j, 0);
        else if (run == clues[j]) t += countFrom(i + 1, j + 1, 0);
        return t;
    }
}

4.3 约束传播求解器

/** 约束传播求解器：行列候选集交替过滤，候选全同则定值 */
public class NonogramSolver {
    final Nonogram p;
    final List<boolean[]>[] rowOpts;
    final List<boolean[]>[] colOpts;
    int sweeps = 0, backtracks = 0;

    @SuppressWarnings("unchecked")
    public NonogramSolver(Nonogram p) {
        this.p = p;
        this.rowOpts = new List[p.h];
        this.colOpts = new List[p.w];
        for (int r = 0; r < p.h; r++)
            rowOpts[r] = new LineSolver(p.rowClues[r], p.w).allCandidates();
        for (int c = 0; c < p.w; c++) {
            int[] colClue = p.colClues[c];
            colOpts[c] = new LineSolver(colClue, p.h).allCandidates();
        }
    }

    /**
     * 一次传播扫描。
     * 返回值：1 = 有变化（需继续扫描），0 = 已收敛（无变化），-1 = 遇到矛盾
     */
    int propagate() {
        boolean changedOverall = false;

        for (int r = 0; r < p.h; r++) {
            // 过滤：只保留与已知格子一致的候选
            List<boolean[]> keep = new ArrayList<>();
            for (boolean[] cand : rowOpts[r]) {
                boolean ok = true;
                for (int c = 0; c < p.w; c++) {
                    int g = p.grid[r][c];
                    if (g != 0 && (cand[c] ? 1 : -1) != g) { ok = false; break; }
                }
                if (ok) keep.add(cand);
            }
            if (keep.isEmpty()) return -1;             // 该行无解 -> 矛盾
            rowOpts[r] = keep;

            // 定值：某格在所有候选中取值一致
            for (int c = 0; c < p.w; c++) {
                if (p.grid[r][c] != 0) continue;
                boolean hasBlack = false, hasWhite = false;
                for (boolean[] cand : keep) {
                    if (cand[c]) hasBlack = true; else hasWhite = true;
                    if (hasBlack && hasWhite) break;
                }
                if (hasBlack && !hasWhite) { p.grid[r][c] = 1; changedOverall = true; }
                else if (!hasBlack && hasWhite) { p.grid[r][c] = -1; changedOverall = true; }
            }
        }

        for (int c = 0; c < p.w; c++) {
            List<boolean[]> keep = new ArrayList<>();
            for (boolean[] cand : colOpts[c]) {
                boolean ok = true;
                for (int r = 0; r < p.h; r++) {
                    int g = p.grid[r][c];
                    if (g != 0 && (cand[r] ? 1 : -1) != g) { ok = false; break; }
                }
                if (ok) keep.add(cand);
            }
            if (keep.isEmpty()) return -1;
            colOpts[c] = keep;

            for (int r = 0; r < p.h; r++) {
                if (p.grid[r][c] != 0) continue;
                boolean hasBlack = false, hasWhite = false;
                for (boolean[] cand : keep) {
                    if (cand[r]) hasBlack = true; else hasWhite = true;
                    if (hasBlack && hasWhite) break;
                }
                if (hasBlack && !hasWhite) { p.grid[r][c] = 1; changedOverall = true; }
                else if (!hasBlack && hasWhite) { p.grid[r][c] = -1; changedOverall = true; }
            }
        }
        return changedOverall ? 1 : 0;
    }

    /** 主求解：传播到不动点；若仍有未知格子，则分支回溯 */
    boolean solve() {
        while (true) {
            sweeps++;
            int r = propagate();
            if (r < 0) return false;      // 矛盾，此分支不可行
            if (r == 0) break;            // 已收敛
        }

        // 找一个未知格子，取候选数最少的（MRV 启发式）
        int br = -1, bc = -1, bestScore = Integer.MAX_VALUE;
        for (int r = 0; r < p.h; r++)
            for (int c = 0; c < p.w; c++)
                if (p.grid[r][c] == 0) {
                    int score = rowOpts[r].size() + colOpts[c].size();
                    if (score < bestScore) { bestScore = score; br = r; bc = c; }
                }
        if (br < 0) return true;       // 无未知格子 -> 解完

        // 分支：先试黑
        for (int val : new int[]{1, -1}) {
            int[][] snapshot = cloneGrid();
            @SuppressWarnings("unchecked")
            List<boolean[]>[] ro = rowOpts.clone();
            @SuppressWarnings("unchecked")
            List<boolean[]>[] co = colOpts.clone();

            p.grid[br][bc] = val;
            if (solve()) return true;

            // 回溯
            backtracks++;
            for (int r = 0; r < p.h; r++) p.grid[r] = snapshot[r].clone();
            System.arraycopy(ro, 0, rowOpts, 0, ro.length);
            System.arraycopy(co, 0, colOpts, 0, co.length);
        }
        return false;
    }

    int[][] cloneGrid() {
        int[][] g = new int[p.h][];
        for (int r = 0; r < p.h; r++) g[r] = p.grid[r].clone();
        return g;
    }

    void print() {
        for (int r = 0; r < p.h; r++) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < p.w; c++)
                sb.append(p.grid[r][c] == 1 ? '#' : (p.grid[r][c] == -1 ? '.' : '?'));
            System.out.println(sb);
        }
        System.out.println("扫描轮数 = " + sweeps + "，回溯次数 = " + backtracks);
    }
}

4.4 主程序

public class NonogramDemo {
    public static void main(String[] args) {
        int[][] rowClues = {{2,2},{7},{10},{8},{6},{4},{2},{2},{},{}};
        int[][] colClues = {{1},{3},{5},{6},{7},{7},{6},{5},{2},{1}};

        Nonogram p = new Nonogram(rowClues, colClues);
        NonogramSolver solver = new NonogramSolver(p);

        // 先看看每行候选数，评估问题难度
        for (int r = 0; r < p.h; r++)
            System.out.print(new LineSolver(p.rowClues[r], p.w).count() + " ");
        System.out.println();

        if (solver.solve()) {
            solver.print();
        } else {
            System.out.println("无解");
        }
    }
}

五、实测结果

5.1 候选数分布

行候选数: 21 4 1 3 5 7 9 9 1 1
列候选数: 10 8 6 5 4 4 5 6 9 10

这一组数字解释了谜题的难度结构：

• 第 3 行 [10] 只有 1 个候选——整行全黑，直接确定 10 个格子；
• 第 9、10 行线索为空（[]），也只有 1 个候选——整行全白；
• 最难的是第 1 行 [2,2]，有 21 个候选，是唯一「真正有歧义」的行。

传播算法的效率完全取决于这种「强约束」的分布：只要有几个 1-候选的行列，传播就能沿着它们迅速扩散。

5.2 传播过程

扫描 1 轮后待定格子 = 22
扫描 2 轮后待定格子 = 0
最终：扫描轮数 = 3（第 3 轮用于确认收敛），回溯次数 = 0

第 1 轮就能定掉 78 个格子（100 格中的 78%），靠的是「1-候选行」的强约束：第 3 行 [10] 全黑、第 9/10 行全白、第 4 列到第 7 列的 [6][7][7][6] 组合几乎无歧义。剩下的 22 个格子靠第 2 轮的行列交叉验证补齐。

解出来的图：

..##..##..
.#######..
##########
.########.
..######..
...####...
....##....
....##....
..........
..........

这个谜题的拓扑结构决定了它完全不需要回溯：线索的约束强到足以让纯传播收敛。这是数织的一个普遍性质——越「好看」的图案（大块黑、大块白），线索越强，传播越容易收敛；而像素风、噪点风的小图往往需要回溯。

5.3 为什么不用暴力枚举

用数字对比：

差距是 7~9 个数量级。这就是「正确的模型」带来的收益——不是算法更快，而是问题的结构被利用了。

5.4 复杂度

• 单行 DFA：状态数 n × (K+1) × (n+1)，最坏 O(n²K)，实际远小于此（run 受 clues[j] 限制）。重建所有候选的复杂度与候选总数成正比。
• 传播：每轮 O(H × 候选数 × W + W × 候选数 × H)，即 O(HW × avgCandidates)。
• 回溯：最坏指数级（数织也是 NP 完全问题），但 MRV（选候选最少的格子）+ 传播的剪枝通常把实际回溯次数压到 0~几十。
• 空间：所有候选排列的存储是主要开销。10×10 谜题的候选总量在几千条，每条 10 个 boolean，内存占用 < 100KB。

六、几个容易踩的坑

1. run == 0 时的白格转移写错。 很多人把「白格」转移写成「总是可以走」，这会允许 #.# 这样的非法模式（块之间必须有空格，但 run==0 时连续白格是合法的）。正确逻辑是：run==0 可走白（继续等待块开始），run==clues[j] 可走白（闭合当前块并前进），其余不可走白。
2. 接受条件漏了「最后一块刚好收尾」。 如果线索 [3]、行长 3，读完 3 格后状态是 (j=0, run=3)，此时 j != K，若只用 j == K 判定会漏掉这个解。正确条件是 j == K || (j == K-1 && run == clues[j])。
3. 传播时用「候选集大小」代替「格子值唯一」。 一行有 5 个候选，不代表能定值。必须逐格检查「是否所有候选取值一致」。
4. 回溯时忘了快照候选集。 只快照 grid 是不够的——rowOpts/colOpts 也被过滤过。恢复时必须连候选集一起还原，否则回溯后的状态是脏的。
5. 不要用 boolean 表示网格。 必须能表达「未知」，否则传播无从下手。

七、可继续改进的方向

1. 重叠法（Overlap）。对单行线索 [a,b,c]，如果所有候选的最小公共黑区存在，可以一次性定值而不需要枚举全部候选。这是人工解数织的主力技巧，也可以作为传播的快速前置。
2. 概率传播。对每个未知格统计「候选中为黑的比例」，优先选择最接近 50% 的格子分支——这比 MRV 在难谜题上更有效。
3. 2-SAT / 精确覆盖建模。把数织转化为精确覆盖问题，用 DLX 求解，适合超大谜题。
4. 线索拆分（clue splitting）。把长行线索拆成前后两段，用「前后缀 DP」加速单行求解，把 O(n²K) 降到 O(nK)。

八、小结

数织是「把约束变成自动机」这一思想的完美教材。一行天然就是一个 DFA，这个观察把「枚举所有可能」变成了「在状态图上做 DP」。DP 给出两样东西：候选总数（难度评估）和候选列表（传播素材）。

接下来是纯工程：把候选列表当作值域，做 AC-3 风格的过滤与定值。整个过程没有搜索，只有收缩。当收缩到不动点时，剩下的歧义才需要回溯——而对结构良好的谜题，这种歧义往往完全不存在。

这套「自动机建模 + 约束传播 + 必要时回溯」的三段式结构，可以直接迁移到数独、肯肯、数桥、帐篷谜题等所有格点逻辑谜题。真正需要记的不是代码，而是这个判断：问题的约束结构是否能被一个状态机表达？ 能，就用 DP；不能，才回到搜索。