Nonogram（逻辑绘图方块/数织/绘图方块）是一种经典的逻辑拼图游戏。玩家需要根据每行和每列给出的数字线索，在网格中填充色块，最终还原出一幅隐藏图案。例如线索 “3 2” 表示该行有连续 3 个填充格，之后至少 1 个空格，再之后连续 2 个填充格。本文用 Java 实现 Nonogram 的自动求解器，核心算法结合行/列约束传播（Constraint Propagation）与深度优先回溯（Backtracking）。
核心算法思路
Nonogram 求解是一个典型的约束满足问题（CSP）。每个格子的状态（填充/空白/未知）同时受到所在行和所在列的线索约束。
求解策略分为两层：
- 约束传播（确定性推理）：对每一行/列，根据线索和当前已知格子状态，推断出某些格子必然为填充或必然为空白。这一过程持续迭代，直到没有新的确定性结论可推出。
- 回溯搜索（试探性推理）：当约束传播无法继续推进时，选择一个未知格子进行假设（先假设为填充），然后再次启动约束传播。如果出现矛盾（某行/列无解），则回退并尝试另一分支（假设为空白）。
行的确定性填充分析是核心。给定一行长度 N 和线索列表 clues = [a, b, c…]，以及该行当前已知的一些填充/空白状态，需要计算出哪些格子是”必然填充”或”必然空白”。常用方法是枚举该行所有与已知状态不矛盾的合法填充模式，然后对所有合法模式求交集——交集中被所有模式填充的格子就是”必然填充”，被所有模式留空的格子就是”必然空白”。
Java 实现
import java.util.*;
public class NonogramSolver {
private int rows, cols;
private List<List<Integer>> rowClues;
private List<List<Integer>> colClues;
// 格子状态: 0=未知, 1=填充, 2=空白
private int[][] grid;
public NonogramSolver(int rows, int cols,
List<List<Integer>> rowClues,
List<List<Integer>> colClues) {
this.rows = rows;
this.cols = cols;
this.rowClues = rowClues;
this.colClues = colClues;
this.grid = new int[rows][cols];
}
/**
* 主求解入口
*/
public boolean solve() {
// 先进行约束传播
boolean changed;
do {
changed = propagateConstraints();
} while (changed);
// 检查是否已完全求解
if (isSolved()) return true;
// 寻找第一个未知格子进行回溯
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 0) {
// 尝试填充
NonogramSolver copy = this.deepCopy();
copy.grid[r][c] = 1;
if (copy.solve()) {
this.grid = copy.grid;
return true;
}
// 尝试空白
copy = this.deepCopy();
copy.grid[r][c] = 2;
if (copy.solve()) {
this.grid = copy.grid;
return true;
}
return false; // 两种假设都失败
}
}
}
return false;
}
/**
* 约束传播：迭代处理所有行和列
*/
private boolean propagateConstraints() {
boolean anyChanged = false;
for (int r = 0; r < rows; r++) {
if (propagateLine(r, true)) anyChanged = true;
}
for (int c = 0; c < cols; c++) {
if (propagateLine(c, false)) anyChanged = true;
}
return anyChanged;
}
/**
* 对单行或单列进行约束传播
* @param idx 行号或列号
* @param isRow true=行, false=列
*/
private boolean propagateLine(int idx, boolean isRow) {
int len = isRow ? cols : rows;
int[] line = new int[len];
List<Integer> clues = isRow ? rowClues.get(idx) : colClues.get(idx);
for (int i = 0; i < len; i++) {
line[i] = isRow ? grid[idx][i] : grid[i][idx];
}
// 枚举所有合法模式
List<int[]> validPatterns = new ArrayList<>();
generateValidPatterns(line, clues, 0, 0, new int[len], validPatterns);
if (validPatterns.isEmpty()) {
throw new IllegalStateException("No valid pattern for line " + idx);
}
// 过滤与已知状态矛盾的模式
List<int[]> filtered = new ArrayList<>();
for (int[] pattern : validPatterns) {
boolean ok = true;
for (int i = 0; i < len; i++) {
if (line[i] != 0 && line[i] != pattern[i]) {
ok = false; break;
}
}
if (ok) filtered.add(pattern);
}
if (filtered.isEmpty()) {
throw new IllegalStateException("Contradiction at line " + idx);
}
// 求交集：所有模式一致的位置可以确定为该状态
boolean changed = false;
for (int i = 0; i < len; i++) {
if (line[i] != 0) continue; // 已知状态不再处理
int firstVal = filtered.get(0)[i];
boolean allSame = true;
for (int[] p : filtered) {
if (p[i] != firstVal) { allSame = false; break; }
}
if (allSame) {
if (isRow) grid[idx][i] = firstVal;
else grid[i][idx] = firstVal;
changed = true;
}
}
return changed;
}
/**
* 递归生成某行/列的所有合法填充模式
*/
private void generateValidPatterns(int[] line, List<Integer> clues,
int clueIdx, int startPos,
int[] current, List<int[]> results) {
if (clueIdx == clues.size()) {
// 剩余位置全部留空
int[] pattern = current.clone();
for (int i = startPos; i < line.length; i++) {
if (line[i] == 1) return; // 矛盾：已知为填充但留空
pattern[i] = 2;
}
results.add(pattern);
return;
}
int clue = clues.get(clueIdx);
int remainingClues = 0;
for (int i = clueIdx; i < clues.size(); i++) remainingClues += clues.get(i);
int minSpace = remainingClues + (clues.size() - clueIdx - 1);
for (int pos = startPos; pos <= line.length - minSpace; pos++) {
// 检查 [startPos, pos) 区间能否留空
boolean ok = true;
for (int i = startPos; i < pos && ok; i++) {
if (line[i] == 1) ok = false; // 已知填充不能留空
}
if (!ok) continue;
// 检查 [pos, pos+clue) 区间能否填充
for (int i = pos; i < pos + clue && ok; i++) {
if (line[i] == 2) ok = false; // 已知空白不能填充
}
if (!ok) continue;
// 创建当前分支的副本
int[] next = current.clone();
for (int i = startPos; i < pos; i++) next[i] = 2;
for (int i = pos; i < pos + clue; i++) next[i] = 1;
int nextStart = pos + clue;
if (clueIdx < clues.size() - 1) {
if (nextStart < line.length) {
if (line[nextStart] == 1) continue; // 需要空格但已知填充
next[nextStart] = 2;
nextStart++;
}
}
generateValidPatterns(line, clues, clueIdx + 1, nextStart, next, results);
}
}
private boolean isSolved() {
for (int[] row : grid) {
for (int cell : row) {
if (cell == 0) return false;
}
}
return true;
}
private NonogramSolver deepCopy() {
NonogramSolver copy = new NonogramSolver(rows, cols, rowClues, colClues);
for (int r = 0; r < rows; r++) {
copy.grid[r] = this.grid[r].clone();
}
return copy;
}
public void printGrid() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
System.out.print(grid[r][c] == 1 ? "██" : grid[r][c] == 2 ? "··" : "??");
}
System.out.println();
}
}
public static void main(String[] args) {
// 示例：5x5 的 Nonogram，图案为一个 "L" 形
List<List<Integer>> rowClues = Arrays.asList(
Arrays.asList(1),
Arrays.asList(1),
Arrays.asList(1),
Arrays.asList(1),
Arrays.asList(5)
);
List<List<Integer>> colClues = Arrays.asList(
Arrays.asList(4),
Arrays.asList(1),
Arrays.asList(1),
Arrays.asList(1),
Arrays.asList(1)
);
NonogramSolver solver = new NonogramSolver(5, 5, rowClues, colClues);
if (solver.solve()) {
System.out.println("Solved!");
solver.printGrid();
} else {
System.out.println("No solution found.");
}
}
}
复杂度分析
时间复杂度：约束传播每轮需要遍历所有行/列，每行/列生成合法模式的数量最坏情况下为 C(N, K) 级别（N 为长度，K 为填充总数），但通常实际谜题的设计使得约束传播能快速收敛。回溯搜索在最坏情况下需要遍历所有 2^(R×C) 种状态，但通过约束传播的大量剪枝，实际运行效率非常高。
空间复杂度：存储网格和递归栈，O(R×C)。
算法优化
- 高效交集计算：不必每次都重新生成所有合法模式，可以维护每行/列当前可能的模式集合，在格子状态变化时增量更新。
- 启发式选择：回溯时优先选择”约束最强”的格子（即所属行/列未知格最少或线索最严格的格子），能更快触发矛盾回退。
- 双向传播：每次修改一个格子后，立即对其所在的行和列进行传播，形成级联推理，而非逐轮扫描。
总结
Nonogram 求解器是约束满足问题的经典范例。行/列约束传播负责处理所有可以逻辑推导的部分，将搜索空间大幅压缩；回溯搜索则处理那些需要试探的决策点。两者结合使得求解器能够高效地解决大多数标准难度的 Nonogram 谜题，同时也展示了 CSP 问题求解的一般框架。
