每日算法 — 使用java实现Nonogram：约束满足与回溯求解

引言

Nonogram（又称绘图方块、数织）是一种逻辑填色谜题。玩家根据网格边缘的数字提示，推断出哪些格子应该被填充，最终揭示一幅隐藏的图案。每行/列的数字表示该行/列中连续填充块的个数与顺序。本文用Java实现一个Nonogram求解器，核心采用约束传播与回溯搜索相结合的策略，配合启发式变量排序，实现高效求解。

问题建模

Nonogram可以建模为约束满足问题（CSP）。设网格为 m × n，每个变量是一个格子的状态（填充/空白）。约束来自行和列的数字提示序列。例如，提示 [3, 1] 表示该行存在长度为3的连续填充块，其后至少间隔一个空格，再接长度为1的填充块。

核心算法：约束传播 + 回溯

求解流程分为三步：
1. 行/列单独求解：根据提示，利用动态规划计算每行/列每个格子的可行状态（必定填充、必定空白、不确定）。
2. 约束传播：将行/列的确定性结论交叉传播，反复迭代直到无法推导新信息。
3. 回溯搜索：若约束传播后仍有不确定格子，选择分支因子最小的变量（MRV启发式），分别假设为填充和空白，递归求解。

行求解器（动态规划）

对单行而言，给定提示序列，可用DP判断每个位置是否可能属于某个填充块。状态定义为 dp[j][k]：处理到第 j 个格子，已匹配前 k 个提示的可行性。通过前向/后向遍历，可标记每个格子的三种状态。

Java实现

import java.util.*;

/**
 * Nonogram求解器：约束传播 + 回溯搜索
 */
public class NonogramSolver {
    private int rows, cols;
    private int[][] rowHints; // 每行的提示
    private int[][] colHints; // 每列的提示
    // 每个格子的状态：0=未知, 1=填充, 2=空白
    private int[][] grid;
    private boolean solved = false;

    public NonogramSolver(int[][] rowHints, int[][] colHints) {
        this.rowHints = rowHints;
        this.colHints = colHints;
        this.rows = rowHints.length;
        this.cols = colHints.length;
        this.grid = new int[rows][cols];
    }

    /**
     * 求解入口：先约束传播，再回溯
     */
    public boolean solve() {
        // 初始化：对每行每列做单独求解，标记确定性格子
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int r = 0; r < rows; r++) {
                changed |= solveLine(r, true);
            }
            for (int c = 0; c < cols; c++) {
                changed |= solveLine(c, false);
            }
        }
        // 若全部确定，检查一致性
        if (isComplete()) {
            return isConsistent();
        }
        // 选择MRV变量进行回溯
        int[] var = selectMRV();
        if (var == null) return false;
        int r = var[0], c = var[1];
        for (int val : new int[]{1, 2}) {
            int[][] backup = copyGrid();
            grid[r][c] = val;
            if (isLocallyConsistent(r, c)) {
                if (solve()) return true;
            }
            grid = backup;
        }
        grid[r][c] = 0;
        return false;
    }

    /**
     * 对单行或单列做约束求解，返回是否产生新确定性结论
     */
    private boolean solveLine(int idx, boolean isRow) {
        int len = isRow ? cols : rows;
        int[] hints = isRow ? rowHints[idx] : colHints[idx];
        // 使用DP计算每个格子的可能状态
        // lineStates[i] = 该位置所有可行解的按位或（1=填充出现, 2=空白出现）
        int[] lineStates = new int[len];
        Arrays.fill(lineStates, 0);
        // 生成所有满足提示的排列，累加状态
        List<int[]> validConfigs = generateValidConfigs(len, hints);
        if (validConfigs.isEmpty()) return false;
        for (int[] cfg : validConfigs) {
            for (int i = 0; i < len; i++) {
                lineStates[i] |= cfg[i]; // cfg[i] 为 1 或 2
            }
        }
        boolean changed = false;
        for (int i = 0; i < len; i++) {
            int pos = isRow ? idx * cols + i : i * cols + idx;
            int r = pos / cols;
            int c = pos % cols;
            if (grid[r][c] != 0) continue;
            if (lineStates[i] == 1) {
                grid[r][c] = 1; // 必定填充
                changed = true;
            } else if (lineStates[i] == 2) {
                grid[r][c] = 2; // 必定空白
                changed = true;
            }
        }
        return changed;
    }

    /**
     * 生成满足行/列提示的所有可能配置
     */
    private List<int[]> generateValidConfigs(int len, int[] hints) {
        List<int[]> result = new ArrayList<>();
        if (hints.length == 1 && hints[0] == 0) {
            int[] cfg = new int[len];
            Arrays.fill(cfg, 2);
            result.add(cfg);
            return result;
        }
        int sum = Arrays.stream(hints).sum();
        int gaps = hints.length - 1;
        int free = len - sum - gaps; // 额外可分配的空格数
        if (free < 0) return result;
        int[] spaces = new int[hints.length + 1]; // 每段前后及中间的空格数
        generateSpaces(result, spaces, 0, free, len, hints);
        return result;
    }

    private void generateSpaces(List<int[]> result, int[] spaces, int idx, int remaining,
                                 int len, int[] hints) {
        if (idx == spaces.length) {
            if (remaining == 0) {
                result.add(buildConfig(spaces, hints, len));
            }
            return;
        }
        int max = remaining;
        // 中间段至少1个空格（除首尾外）
        if (idx > 0 && idx < spaces.length - 1) {
            // 中间空格至少1个已在gaps中扣除，这里spaces对应额外分配
        }
        for (int v = 0; v <= max; v++) {
            spaces[idx] = v;
            generateSpaces(result, spaces, idx + 1, remaining - v, len, hints);
        }
    }

    private int[] buildConfig(int[] spaces, int[] hints, int len) {
        int[] cfg = new int[len];
        int pos = 0;
        for (int i = 0; i < hints.length; i++) {
            pos += spaces[i]; // 前导空格
            for (int j = 0; j < hints[i]; j++) {
                cfg[pos++] = 1;
            }
            if (i < hints.length - 1) {
                cfg[pos++] = 2; // 提示块之间至少一个空格
            }
        }
        pos += spaces[spaces.length - 1]; // 尾随空格
        while (pos < len) cfg[pos++] = 2;
        return cfg;
    }

    private boolean isComplete() {
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == 0) return false;
        return true;
    }

    private boolean isConsistent() {
        for (int r = 0; r < rows; r++)
            if (!checkLine(r, true)) return false;
        for (int c = 0; c < cols; c++)
            if (!checkLine(c, false)) return false;
        return true;
    }

    private boolean checkLine(int idx, boolean isRow) {
        int len = isRow ? cols : rows;
        int[] hints = isRow ? rowHints[idx] : colHints[idx];
        List<Integer> blocks = new ArrayList<>();
        int count = 0;
        for (int i = 0; i < len; i++) {
            int pos = isRow ? idx * cols + i : i * cols + idx;
            int r = pos / cols, c = pos % cols;
            if (grid[r][c] == 1) {
                count++;
            } else {
                if (count > 0) blocks.add(count);
                count = 0;
            }
        }
        if (count > 0) blocks.add(count);
        if (blocks.size() != hints.length) return false;
        for (int i = 0; i < hints.length; i++)
            if (blocks.get(i) != hints[i]) return false;
        return true;
    }

    private int[] selectMRV() {
        int minOptions = Integer.MAX_VALUE;
        int[] best = null;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != 0) continue;
                int options = countOptions(r, c);
                if (options < minOptions) {
                    minOptions = options;
                    best = new int[]{r, c};
                }
            }
        }
        return best;
    }

    private int countOptions(int r, int c) {
        int opts = 0;
        for (int val : new int[]{1, 2}) {
            grid[r][c] = val;
            if (isLocallyConsistent(r, c)) opts++;
            grid[r][c] = 0;
        }
        return opts;
    }

    private boolean isLocallyConsistent(int r, int c) {
        return checkLinePartial(r, true) && checkLinePartial(c, false);
    }

    private boolean checkLinePartial(int idx, boolean isRow) {
        // 快速检查：若该行/列已全确定，验证是否满足提示
        int len = isRow ? cols : rows;
        boolean complete = true;
        for (int i = 0; i < len; i++) {
            int pos = isRow ? idx * cols + i : i * cols + idx;
            int rr = pos / cols, cc = pos % cols;
            if (grid[rr][cc] == 0) { complete = false; break; }
        }
        if (complete) return checkLine(idx, isRow);
        // 否则检查不可能性：已确定部分是否违反提示
        return true; // 简化处理
    }

    private int[][] copyGrid() {
        int[][] copy = new int[rows][cols];
        for (int r = 0; r < rows; r++)
            System.arraycopy(grid[r], 0, copy[r], 0, cols);
        return copy;
    }

    public void printSolution() {
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                System.out.print(grid[r][c] == 1 ? "■ " : "□ ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 5x5 心形图案提示
        int[][] rowHints = {{2}, {4}, {1,1,1}, {2,2}, {1,1}};
        int[][] colHints = {{2}, {4}, {1,1,1}, {4}, {2}};
        NonogramSolver solver = new NonogramSolver(rowHints, colHints);
        if (solver.solve()) {
            System.out.println("求解成功：");
            solver.printSolution();
        } else {
            System.out.println("无解");
        }
    }
}

复杂度分析

• 约束传播：每轮遍历所有行/列，每行/列生成所有合法配置的时间为 O(C(len, free))，实际通过缓存可大幅优化。
• 回溯搜索：最坏情况下需遍历所有 2^(m×n) 种状态，但约束传播通常可将搜索空间缩减数个数量级。MRV启发式进一步降低分支因子。

扩展方向

• ** Dancing Links（DLX）**：将Nonogram精确覆盖建模，用DLX算法加速求解。
• ** SAT求解器**：将约束编码为合取范式（CNF），调用MiniSat等求解器。
• ** 图形界面**：用Swing/JavaFX实现交互式填色与提示高亮。