每日算法 — 使用java实现数织：行列约束传播与回溯搜索求解

可莉爸爸 AI算法

数织（Nonogram），又称逻辑绘图、日本拼图，是一种经典的逻辑益智游戏。玩家根据每行每列给出的数字提示，推断出哪些格子需要填充，最终揭示一幅隐藏图案。本文将用 Java 实现一个带约束传播的数织自动求解器，讲解如何通过行/列可能排列的动态规划生成、约束传播推断与回溯搜索完成求解。

数织游戏规则

给定一个 m × n 的空白网格，每一行和每一列都有一组数字提示：

  • 行提示表示该行中连续填充格子的长度，多个数字之间至少间隔一个空白格。
  • 列提示同理，表示该列中连续填充格子的长度。

例如，某行长度为 5，提示为 [2, 1]，则表示该行存在 “2 个连续填充格 + 至少 1 个空白格 + 1 个填充格” 的模式。合法的排列有 ##.#. 和 ##..# 等。

玩家的目标是根据所有行提示和列提示，将网格中的每个格子确定为填充、空白或未知，最终使所有行/列都满足对应提示。

算法设计思路

数织求解是一个典型的约束满足问题（CSP）。本文采用约束传播 + 回溯搜索的经典组合策略：

  1. 行/列可能排列生成：对每一行（或列），根据提示和当前已确定的格子，生成所有符合约束的布尔数组排列。
  2. 约束传播：检查某行（或列）的所有可能排列，若某个位置在所有排列中均为 true（填充），则该格确定为填充；若均为 false（空白），则确定为空白。重复执行行传播与列传播，直到网格不再变化。
  3. 回溯搜索：若约束传播后仍有未知格子，则选择一个未知格子进行猜测（先假设填充，再假设空白），对每个假设递归执行约束传播。若某假设导致矛盾（某行/列无合法排列），则剪枝回退。

核心数据结构

enum CellState {
    UNKNOWN('.'),  // 未确定
    FILLED('#'),   // 确定填充
    EMPTY(' ');    // 确定空白
    final char symbol;
    CellState(char c) { this.symbol = c; }
}

每个格子的状态只有三种。求解过程就是从全 UNKNOWN 出发，通过传播和搜索，逐步确定为 FILLED 或 EMPTY。

行/列可能排列的递归生成

对于一行（或一列），在已知部分格子状态的情况下，需要生成所有满足提示且不与已知状态冲突的排列。采用递归回溯生成：

/**
 * 递归生成一行/一列的所有合法排列
 * @param result   存储结果的列表
 * @param current  当前构建的布尔数组（true=填充, false=空白）
 * @param hints    该行/列的提示数字
 * @param hintIdx  当前处理到第几个hint
 * @param pos      当前处理到数组的哪个位置
 * @param filledCount 当前连续填充的长度（用于校验）
 * @param known    该行/列当前已知的格子状态
 */
private void backtrack(List<boolean[]> result, boolean[] current,
                       int[] hints, int hintIdx, int pos, int filledCount,
                       CellState[] known) {
    // 如果已经处理完所有位置
    if (pos == current.length) {
        // 校验最后一个hint是否刚好结束
        if (hintIdx == hints.length && filledCount == 0) {
            result.add(current.clone());
        } else if (hintIdx == hints.length - 1 && filledCount == hints[hintIdx]) {
            result.add(current.clone());
        }
        return;
    }

    // 如果已知当前位置必须是EMPTY
    if (known[pos] == CellState.EMPTY) {
        if (filledCount > 0) {
            // 如果前面有连续填充，必须刚好匹配当前hint
            if (hintIdx >= hints.length || filledCount != hints[hintIdx]) {
                return; // 矛盾，剪枝
            }
            hintIdx++;
        }
        current[pos] = false;
        backtrack(result, current, hints, hintIdx, pos + 1, 0, known);
    }
    // 如果已知当前位置必须是FILLED
    else if (known[pos] == CellState.FILLED) {
        if (hintIdx >= hints.length) return; // 没有更多hint但需要填充，矛盾
        if (filledCount + 1 > hints[hintIdx]) return; // 连续填充超过hint，矛盾
        current[pos] = true;
        backtrack(result, current, hints, hintIdx, pos + 1, filledCount + 1, known);
    }
    // 未知位置，尝试两种可能
    else {
        // 尝试EMPTY
        if (filledCount == 0) {
            // 前面没有连续填充，直接放空白
            current[pos] = false;
            backtrack(result, current, hints, hintIdx, pos + 1, 0, known);
        } else {
            // 前面有连续填充，必须刚好结束当前hint
            if (hintIdx < hints.length && filledCount == hints[hintIdx]) {
                current[pos] = false;
                backtrack(result, current, hints, hintIdx + 1, pos + 1, 0, known);
            }
            // 否则不能放空白，因为会中断不合法的连续段
        }

        // 尝试FILLED
        if (hintIdx < hints.length && filledCount + 1 <= hints[hintIdx]) {
            current[pos] = true;
            backtrack(result, current, hints, hintIdx, pos + 1, filledCount + 1, known);
        }
    }
}

该递归函数通过 known 数组过滤掉与已知状态冲突的分支，有效减少搜索空间。

约束传播的实现

约束传播是求解器的核心加速手段。对每一行（或列），生成所有合法排列后，检查每个位置在所有排列中是否取值一致：

/**
 * 对指定行/列执行约束传播
 * @param idx 行号或列号
 * @param isRow true表示处理行，false表示处理列
 * @return 如果成功推断出新的确定格子，返回true
 */
private boolean propagateLine(int idx, boolean isRow) {
    int len = isRow ? cols : rows;
    CellState[] known = new CellState[len];
    for (int i = 0; i < len; i++) {
        known[i] = isRow ? grid[idx][i] : grid[i][idx];
    }
    int[] hints = isRow ? rowHints[idx] : colHints[idx];

    List<boolean[]> possibilities = new ArrayList<>();
    backtrack(possibilities, new boolean[len], hints, 0, 0, 0, known);

    // 如果没有合法排列，说明当前状态矛盾
    if (possibilities.isEmpty()) {
        throw new IllegalStateException("矛盾状态");
    }

    boolean changed = false;
    for (int i = 0; i < len; i++) {
        if (known[i] != CellState.UNKNOWN) continue;

        boolean allFilled = true;
        boolean allEmpty = true;
        for (boolean[] p : possibilities) {
            if (!p[i]) allFilled = false;
            if (p[i]) allEmpty = false;
        }

        if (allFilled) {
            if (isRow) grid[idx][i] = CellState.FILLED;
            else grid[i][idx] = CellState.FILLED;
            changed = true;
        } else if (allEmpty) {
            if (isRow) grid[idx][i] = CellState.EMPTY;
            else grid[i][idx] = CellState.EMPTY;
            changed = true;
        }
    }
    return changed;
}

约束传播的关键在于循环执行：行传播可能导致某些列的新约束，列传播又可能进一步确定某些行的格子。因此需要反复迭代，直到没有新格子被确定。

/**
 * 全局约束传播，循环执行直到不再变化
 * @return 如果传播过程中出现矛盾，返回false
 */
private boolean propagate() {
    boolean changed = true;
    while (changed) {
        changed = false;
        try {
            for (int r = 0; r < rows; r++) {
                if (propagateLine(r, true)) changed = true;
            }
            for (int c = 0; c < cols; c++) {
                if (propagateLine(c, false)) changed = true;
            }
        } catch (IllegalStateException e) {
            return false; // 出现矛盾
        }
    }
    return true;
}

回溯搜索与递归求解

对于许多数织谜题，仅靠约束传播就能完全求解。但对于复杂谜题，传播后会残留未知格子，此时需要回溯搜索：

/**
 * 求解主入口
 * @return 是否成功求解
 */
public boolean solve() {
    if (!propagate()) return false;

    // 检查是否已全部确定
    int unknownR = -1, unknownC = -1;
    outer:
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == CellState.UNKNOWN) {
                unknownR = r;
                unknownC = c;
                break outer;
            }
        }
    }
    if (unknownR == -1) return true; // 全部确定，求解成功

    // 复制当前状态，尝试假设当前格子为FILLED
    NonogramSolver filledSolver = clone();
    filledSolver.grid[unknownR][unknownC] = CellState.FILLED;
    if (filledSolver.solve()) {
        this.copyFrom(filledSolver);
        return true;
    }

    // 尝试假设当前格子为EMPTY
    NonogramSolver emptySolver = clone();
    emptySolver.grid[unknownR][unknownC] = CellState.EMPTY;
    if (emptySolver.solve()) {
        this.copyFrom(emptySolver);
        return true;
    }

    return false;
}

这里采用深度优先搜索策略。为了提升效率，可以进一步优化为选择”约束最强”的未知格子（即行/列可能排列最少的格子）进行猜测，从而更快触发矛盾剪枝。

完整可运行代码

以下是完整的 Java 项目代码，包含求解器类和主函数示例：

import java.util.*;

/**
 * 数织（Nonogram）自动求解器
 * 采用约束传播 + 回溯搜索策略
 */
public class NonogramSolver {
    enum CellState {
        UNKNOWN('.'),
        FILLED('#'),
        EMPTY(' ');
        final char symbol;
        CellState(char c) { this.symbol = c; }
    }

    private final int rows;
    private final int cols;
    private final int[][] rowHints;
    private final int[][] colHints;
    private final CellState[][] grid;

    public NonogramSolver(int[][] rowHints, int[][] colHints) {
        this.rowHints = rowHints;
        this.colHints = colHints;
        this.rows = rowHints.length;
        this.cols = colHints.length;
        this.grid = new CellState[rows][cols];
        for (int i = 0; i < rows; i++) {
            Arrays.fill(grid[i], CellState.UNKNOWN);
        }
    }

    private NonogramSolver(NonogramSolver other) {
        this.rows = other.rows;
        this.cols = other.cols;
        this.rowHints = other.rowHints;
        this.colHints = other.colHints;
        this.grid = new CellState[rows][cols];
        for (int r = 0; r < rows; r++) {
            System.arraycopy(other.grid[r], 0, this.grid[r], 0, cols);
        }
    }

    private NonogramSolver clone() {
        return new NonogramSolver(this);
    }

    private void copyFrom(NonogramSolver other) {
        for (int r = 0; r < rows; r++) {
            System.arraycopy(other.grid[r], 0, this.grid[r], 0, cols);
        }
    }

    // ========== 行/列排列生成 ==========

    private void backtrack(List<boolean[]> result, boolean[] current,
                           int[] hints, int hintIdx, int pos, int filledCount,
                           CellState[] known) {
        if (pos == current.length) {
            if (hintIdx == hints.length && filledCount == 0) {
                result.add(current.clone());
            } else if (hintIdx == hints.length - 1 && filledCount == hints[hintIdx]) {
                result.add(current.clone());
            }
            return;
        }

        if (known[pos] == CellState.EMPTY) {
            if (filledCount > 0) {
                if (hintIdx >= hints.length || filledCount != hints[hintIdx]) return;
                hintIdx++;
            }
            current[pos] = false;
            backtrack(result, current, hints, hintIdx, pos + 1, 0, known);
        } else if (known[pos] == CellState.FILLED) {
            if (hintIdx >= hints.length) return;
            if (filledCount + 1 > hints[hintIdx]) return;
            current[pos] = true;
            backtrack(result, current, hints, hintIdx, pos + 1, filledCount + 1, known);
        } else {
            // 尝试EMPTY
            if (filledCount == 0) {
                current[pos] = false;
                backtrack(result, current, hints, hintIdx, pos + 1, 0, known);
            } else {
                if (hintIdx < hints.length && filledCount == hints[hintIdx]) {
                    current[pos] = false;
                    backtrack(result, current, hints, hintIdx + 1, pos + 1, 0, known);
                }
            }
            // 尝试FILLED
            if (hintIdx < hints.length && filledCount + 1 <= hints[hintIdx]) {
                current[pos] = true;
                backtrack(result, current, hints, hintIdx, pos + 1, filledCount + 1, known);
            }
        }
    }

    // ========== 约束传播 ==========

    private boolean propagateLine(int idx, boolean isRow) throws IllegalStateException {
        int len = isRow ? cols : rows;
        CellState[] known = new CellState[len];
        for (int i = 0; i < len; i++) {
            known[i] = isRow ? grid[idx][i] : grid[i][idx];
        }
        int[] hints = isRow ? rowHints[idx] : colHints[idx];

        List<boolean[]> possibilities = new ArrayList<>();
        backtrack(possibilities, new boolean[len], hints, 0, 0, 0, known);

        if (possibilities.isEmpty()) {
            throw new IllegalStateException("矛盾");
        }

        boolean changed = false;
        for (int i = 0; i < len; i++) {
            if (known[i] != CellState.UNKNOWN) continue;
            boolean allFilled = true, allEmpty = true;
            for (boolean[] p : possibilities) {
                if (!p[i]) allFilled = false;
                if (p[i]) allEmpty = false;
            }
            if (allFilled) {
                if (isRow) grid[idx][i] = CellState.FILLED;
                else grid[i][idx] = CellState.FILLED;
                changed = true;
            } else if (allEmpty) {
                if (isRow) grid[idx][i] = CellState.EMPTY;
                else grid[i][idx] = CellState.EMPTY;
                changed = true;
            }
        }
        return changed;
    }

    private boolean propagate() {
        boolean changed = true;
        while (changed) {
            changed = false;
            try {
                for (int r = 0; r < rows; r++) {
                    if (propagateLine(r, true)) changed = true;
                }
                for (int c = 0; c < cols; c++) {
                    if (propagateLine(c, false)) changed = true;
                }
            } catch (IllegalStateException e) {
                return false;
            }
        }
        return true;
    }

    // ========== 回溯搜索 ==========

    public boolean solve() {
        if (!propagate()) return false;

        int targetR = -1, targetC = -1;
        outer:
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == CellState.UNKNOWN) {
                    targetR = r;
                    targetC = c;
                    break outer;
                }
            }
        }
        if (targetR == -1) return true;

        NonogramSolver filled = clone();
        filled.grid[targetR][targetC] = CellState.FILLED;
        if (filled.solve()) {
            copyFrom(filled);
            return true;
        }

        NonogramSolver empty = clone();
        empty.grid[targetR][targetC] = CellState.EMPTY;
        if (empty.solve()) {
            copyFrom(empty);
            return true;
        }

        return false;
    }

    // ========== 输出与展示 ==========

    public void printGrid() {
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                System.out.print(grid[r][c].symbol);
                System.out.print(' ');
            }
            System.out.println();
        }
    }

    public boolean isSolved() {
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == CellState.UNKNOWN) return false;
            }
        }
        return true;
    }

    // ========== 主函数：示例谜题 ==========

    public static void main(String[] args) {
        // 示例：5x5 的简单数织，最终图案为字母 "L"
        // 行提示
        int[][] rowHints = {
            {5},      // 第0行：5个连续填充
            {1},      // 第1行：1个填充
            {1},      // 第2行：1个填充
            {1},      // 第3行：1个填充
            {1}       // 第4行：1个填充
        };
        // 列提示
        int[][] colHints = {
            {5},      // 第0列
            {1},      // 第1列
            {1},      // 第2列
            {1},      // 第3列
            {1}       // 第4列
        };

        System.out.println("=== 示例1：5x5 简单数织 ===");
        NonogramSolver solver1 = new NonogramSolver(rowHints, colHints);
        if (solver1.solve()) {
            System.out.println("求解成功：");
            solver1.printGrid();
        } else {
            System.out.println("无解");
        }

        // 示例2：10x10 中等难度谜题（心形图案）
        int[][] rowHints2 = {
            {2, 2},
            {4, 4},
            {10},
            {10},
            {8},
            {6},
            {4},
            {2},
            {0},
            {0}
        };
        int[][] colHints2 = {
            {3},
            {5},
            {6},
            {7},
            {7},
            {7},
            {7},
            {6},
            {5},
            {3}
        };

        System.out.println("\n=== 示例2：10x10 心形数织 ===");
        NonogramSolver solver2 = new NonogramSolver(rowHints2, colHints2);
        if (solver2.solve()) {
            System.out.println("求解成功：");
            solver2.printGrid();
        } else {
            System.out.println("无解");
        }
    }
}

编译并运行上述代码，可以直接看到两个数织谜题的求解结果。

算法复杂度分析

设网格大小为 m × n：

  • 行/列排列生成：对于长度为 L 的行/列，提示和为 S，则合法排列数在最坏情况下为 O(C(L, S))，即组合数级别。对于中等规模的数织（如 15×15 以下），排列数通常在可接受范围内。
  • 约束传播：每轮传播需要处理所有行和列，每行/列生成排列的时间为 O(P × L)，其中 P 为合法排列数。由于传播会显著减少未知格子数，实际迭代轮数通常很少。
  • 回溯搜索：最坏情况下需要遍历所有未知格子的组合，时间复杂度为指数级 O(2^(m×n))。但在约束传播的配合下，大量分支会在早期被剪枝，实际求解效率远高于纯回溯。

对于绝大多数标准数织谜题（25×25 以内），约束传播通常能直接解出 60%~90% 的格子，剩余少量未知格子通过回溯即可快速确定。

扩展优化方向

  1. 启发式格子选择：回溯时不按顺序选择未知格子，而是优先选择所在行/列合法排列数最少的格子，这样能更快触发矛盾剪枝。
  2. 缓存行/列排列：在搜索过程中，同一行/列的已知状态可能多次出现，可以使用哈希表缓存其合法排列集合，避免重复生成。
  3. 多线程求解：对于超大规模数织，可以对搜索树的不同分支进行并行探索。

总结

数织求解展示了约束满足问题的经典解法：约束传播缩小搜索空间，回溯搜索处理剩余不确定性。通过 Java 实现的求解器完整地演示了行/列可能排列的递归生成、约束传播的迭代推断以及深度优先的回溯策略。读者可以在此基础上继续探索更高效的启发式搜索、缓存优化或多线程求解方案。

Tagged with: