引言
数织（Nonogram，又称绘图方块、逻辑绘图）是一种源自日本的逻辑谜题。玩家根据每行每列给出的数字提示，在网格中填充色块，最终 reveal 出一幅隐藏的像素画。
与数独类似，数织的求解依赖于约束推理；但数织的约束更为复杂——每行每列的提示描述了一段连续的填充段。本文将用Java实现一个高效的数织求解器，结合约束传播（Constraint Propagation）与回溯搜索（Backtracking）两大核心技术。
游戏规则与约束建模
游戏规则
- 棋盘为 $N \times M$ 的方格
- 每行左侧有一组数字，表示该行中连续填充段的长度
- 每列上方有一组数字，表示该列中连续填充段的长度
- 填充段之间至少有一个空格分隔
- 目标：根据行列提示，确定每个格子是填充（■）还是空白（□）
示例
2 1
1 1
┌──────
3 │□ ■ ■ ■
1 │■ □ □ □
1 │□ □ □ ■
约束建模
每个格子有三种状态：
– UNKNOWN（未知）
– FILLED（已填充）
– EMPTY（已确定空白）
每行/每列的约束可表示为：给定一段长度序列 $[a_1, a_2, …, a_k]$，在长度为 $L$ 的线上放置 $k$ 段连续填充，段间至少一个空格，且总长度不超过 $L$。
核心算法
1. 单行/单列求解（Line Solver）
这是求解器的核心子程序。对于给定的一行（或一列）和对应的提示数字，确定哪些格子必然填充、哪些必然空白。
算法思路：
1. 计算所有满足约束的合法排列
2. 对所有合法排列进行”交集”运算
3. 交集中所有排列都填充的位置标记为FILLED
4. 交集中所有排列都空白的位置标记为EMPTY
2. 约束传播
利用行列之间的耦合关系进行信息传递：
– 当某行确定了某些格子的状态时，这些约束传递到对应列
– 列求解器根据新信息进一步确定其他格子
– 循环往复，直到没有新信息产生
3. 回溯搜索
当约束传播无法完全求解时，选择信息量最大的格子进行猜测：
– 选择一个UNKNOWN格子
– 假设它为FILLED，继续传播
– 如果出现矛盾，回溯并假设为EMPTY
– 重复直到求解或证明无解
Java实现
项目结构
nonogram-solver/
├── src/
│ └── com/
│ └── nonogram/
│ ├── CellState.java // 格子状态枚举
│ ├── LineSolver.java // 单行/单列求解器
│ ├── ConstraintPropagator.java // 约束传播器
│ ├── NonogramBoard.java // 棋盘表示
│ ├── NonogramSolver.java // 主求解器
│ └── Main.java // 入口
基础枚举与棋盘
package com.nonogram;
import java.util.*;
/**
* 格子状态
*/
enum CellState {
UNKNOWN, // 未知（.?）
FILLED, // 填充（■）
EMPTY // 空白（□）
}
/**
* 数织棋盘
*/
class NonogramBoard {
final int rows;
final int cols;
final CellState[][] grid;
final int[][] rowHints; // 每行的提示
final int[][] colHints; // 每列的提示
NonogramBoard(int rows, int cols, int[][] rowHints, int[][] colHints) {
this.rows = rows;
this.cols = cols;
this.rowHints = rowHints;
this.colHints = colHints;
this.grid = new CellState[rows][cols];
for (int i = 0; i < rows; i++) {
Arrays.fill(grid[i], CellState.UNKNOWN);
}
}
/**
* 深拷贝
*/
NonogramBoard(NonogramBoard 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 i = 0; i < rows; i++) {
System.arraycopy(other.grid[i], 0, this.grid[i], 0, cols);
}
}
boolean isSolved() {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == CellState.UNKNOWN) return false;
}
}
return true;
}
boolean isValid() {
// 检查每行每列是否与当前已知状态冲突
for (int r = 0; r < rows; r++) {
if (!isLineValid(getRow(r), rowHints[r])) return false;
}
for (int c = 0; c < cols; c++) {
if (!isLineValid(getCol(c), colHints[c])) return false;
}
return true;
}
/**
* 检查当前行/列状态是否与提示冲突
*/
private boolean isLineValid(CellState[] line, int[] hints) {
// 简单检查：已确定的部分不能违反提示约束
int n = line.length;
// 计算FILLED段，跳过UNKNOWN
List<Integer> filledRuns = new ArrayList<>();
int currentRun = 0;
boolean inRun = false;
for (int i = 0; i <= n; i++) {
if (i < n && line[i] == CellState.FILLED) {
if (!inRun) {
inRun = true;
currentRun = 1;
} else {
currentRun++;
}
} else {
if (inRun) {
filledRuns.add(currentRun);
inRun = false;
}
}
}
// 如果没有UNKNOWN，必须精确匹配
boolean hasUnknown = false;
for (CellState s : line) if (s == CellState.UNKNOWN) hasUnknown = true;
if (!hasUnknown) {
if (filledRuns.size() != hints.length) return false;
for (int i = 0; i < hints.length; i++) {
if (filledRuns.get(i) != hints[i]) return false;
}
return true;
}
// 有UNKNOWN时，检查已确定的段不违反约束
// 已完成的段数不能超过提示数
// 且已完成的段长度必须匹配对应的提示
int completedRuns = 0;
for (int i = 0; i < line.length; i++) {
if (line[i] == CellState.FILLED) {
// 检查这个run是否被EMPTY包围（即已完成）
int start = i;
while (i < line.length && line[i] == CellState.FILLED) i++;
int end = i;
boolean boundedLeft = (start == 0) || (line[start - 1] == CellState.EMPTY);
boolean boundedRight = (end == line.length) || (line[end] == CellState.EMPTY);
if (boundedLeft && boundedRight) {
// 这是一个已完成的run
if (completedRuns >= hints.length) return false;
if (end - start != hints[completedRuns]) return false;
completedRuns++;
}
}
}
return true;
}
CellState[] getRow(int r) {
return grid[r].clone();
}
CellState[] getCol(int c) {
CellState[] col = new CellState[rows];
for (int i = 0; i < rows; i++) col[i] = grid[i][c];
return col;
}
void setRow(int r, CellState[] values) {
System.arraycopy(values, 0, grid[r], 0, cols);
}
void setCol(int c, CellState[] values) {
for (int i = 0; i < rows; i++) grid[i][c] = values[i];
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
sb.append(switch (grid[i][j]) {
case FILLED -> "■ ";
case EMPTY -> "□ ";
case UNKNOWN -> "? ";
});
}
sb.append(" | ");
for (int h : rowHints[i]) sb.append(h).append(" ");
sb.append("\n");
}
sb.append("-".repeat(cols * 2)).append("\n");
for (int j = 0; j < cols; j++) {
sb.append(String.format("%-2d", j % 10));
}
return sb.toString();
}
}
单行求解器
package com.nonogram;
import java.util.*;
/**
* 单行/单列求解器
* 使用递归生成所有合法排列，然后求交集
*/
public class LineSolver {
/**
* 求解单行/单列，返回更新后的状态数组
* @param line 当前行/列状态
* @param hints 提示数字
* @return 新状态，如果矛盾返回null
*/
public static CellState[] solveLine(CellState[] line, int[] hints) {
int n = line.length;
// 收集所有合法排列
List<CellState[]> validPlacements = new ArrayList<>();
generatePlacements(line, hints, 0, 0, new CellState[n], validPlacements);
if (validPlacements.isEmpty()) {
return null; // 矛盾，无解
}
// 求交集
CellState[] result = new CellState[n];
for (int i = 0; i < n; i++) {
boolean allFilled = true;
boolean allEmpty = true;
for (CellState[] placement : validPlacements) {
if (placement[i] != CellState.FILLED) allFilled = false;
if (placement[i] != CellState.EMPTY) allEmpty = false;
}
if (allFilled) result[i] = CellState.FILLED;
else if (allEmpty) result[i] = CellState.EMPTY;
else result[i] = line[i]; // 保持原状态
}
return result;
}
/**
* 递归生成所有与当前已知状态兼容的合法排列
*/
private static void generatePlacements(CellState[] line, int[] hints,
int hintIdx, int startPos,
CellState[] current,
List<CellState[]> results) {
int n = line.length;
// 已处理完所有hints，剩余位置必须EMPTY或与UNKNOWN兼容
if (hintIdx == hints.length) {
for (int i = startPos; i < n; i++) {
if (line[i] == CellState.FILLED) return; // 冲突
current[i] = CellState.EMPTY;
}
// 复制结果
CellState[] copy = new CellState[n];
System.arraycopy(current, 0, copy, 0, n);
results.add(copy);
return;
}
int hint = hints[hintIdx];
// 计算这个位置最早可以开始放置
// 剩余hints所需的最小空间：sum(remaining hints) + (remaining hints count - 1) gaps
int remainingSpace = 0;
for (int i = hintIdx; i < hints.length; i++) remainingSpace += hints[i];
remainingSpace += hints.length - hintIdx - 1; // gaps between hints
int maxStart = n - remainingSpace;
for (int pos = startPos; pos <= maxStart; pos++) {
// 检查从pos到pos+hint-1是否可以全部FILLED
boolean canPlace = true;
for (int i = pos; i < pos + hint && canPlace; i++) {
if (line[i] == CellState.EMPTY) canPlace = false;
}
// 检查hint后面是否有分隔（如果是最后一个hint则不需要）
if (canPlace && hintIdx < hints.length - 1) {
if (pos + hint < n && line[pos + hint] == CellState.FILLED) {
canPlace = false; // 需要至少一个空格分隔
}
}
if (!canPlace) {
// 如果当前位置强制为FILLED但无法放置，直接剪枝
if (pos < n && line[pos] == CellState.FILLED) return;
continue;
}
// 放置hint：pos之前设为EMPTY，hint位置设为FILLED
for (int i = startPos; i < pos; i++) {
if (line[i] == CellState.FILLED) { canPlace = false; break; }
current[i] = CellState.EMPTY;
}
if (!canPlace) continue;
for (int i = pos; i < pos + hint; i++) {
current[i] = CellState.FILLED;
}
// 分隔空格（如果不是最后一个hint）
int nextStart = pos + hint;
if (hintIdx < hints.length - 1) {
if (nextStart < n) current[nextStart] = CellState.EMPTY;
nextStart++;
}
generatePlacements(line, hints, hintIdx + 1, nextStart, current, results);
}
}
}
约束传播器
package com.nonogram;
/**
* 约束传播器
* 反复应用行/列求解器，直到没有新信息产生
*/
public class ConstraintPropagator {
private int propagationRounds = 0;
/**
* 执行约束传播
* @return true如果传播后状态仍然合法
*/
public boolean propagate(NonogramBoard board) {
boolean changed = true;
while (changed) {
changed = false;
propagationRounds++;
// 处理所有行
for (int r = 0; r < board.rows; r++) {
CellState[] oldRow = board.getRow(r);
CellState[] newRow = LineSolver.solveLine(oldRow, board.rowHints[r]);
if (newRow == null) return false; // 矛盾
for (int c = 0; c < board.cols; c++) {
if (oldRow[c] != newRow[c]) {
board.grid[r][c] = newRow[c];
changed = true;
}
}
}
// 处理所有列
for (int c = 0; c < board.cols; c++) {
CellState[] oldCol = board.getCol(c);
CellState[] newCol = LineSolver.solveLine(oldCol, board.colHints[c]);
if (newCol == null) return false; // 矛盾
for (int r = 0; r < board.rows; r++) {
if (oldCol[r] != newCol[r]) {
board.grid[r][c] = newCol[r];
changed = true;
}
}
}
}
return true;
}
public int getPropagationRounds() { return propagationRounds; }
}
主求解器（含回溯）
package com.nonogram;
/**
* 数织主求解器
* 约束传播 + 回溯搜索
*/
public class NonogramSolver {
private int backtrackCount = 0;
private int guessCount = 0;
/**
* 求解数织谜题
*/
public NonogramBoard solve(NonogramBoard board) {
ConstraintPropagator propagator = new ConstraintPropagator();
// 先进行约束传播
if (!propagator.propagate(board)) {
return null; // 矛盾
}
// 如果已解决，直接返回
if (board.isSolved()) {
return board;
}
// 选择最优猜测位置
int[] guessPos = selectGuessPosition(board);
if (guessPos == null) return null;
int r = guessPos[0];
int c = guessPos[1];
guessCount++;
// 尝试 FILLED
NonogramBoard filledBoard = new NonogramBoard(board);
filledBoard.grid[r][c] = CellState.FILLED;
NonogramBoard filledResult = solve(filledBoard);
if (filledResult != null) return filledResult;
// 尝试 EMPTY
NonogramBoard emptyBoard = new NonogramBoard(board);
emptyBoard.grid[r][c] = CellState.EMPTY;
backtrackCount++;
return solve(emptyBoard);
}
/**
* 选择最优猜测位置
* 策略：选择约束最强的行/列交点（UNKNOWN最少的那行/列）
*/
private int[] selectGuessPosition(NonogramBoard board) {
int bestR = -1, bestC = -1;
int bestScore = Integer.MAX_VALUE;
for (int r = 0; r < board.rows; r++) {
for (int c = 0; c < board.cols; c++) {
if (board.grid[r][c] != CellState.UNKNOWN) continue;
// 评分：该行该列的已知信息越多越优先
int rowKnown = 0, colKnown = 0;
for (int j = 0; j < board.cols; j++) {
if (board.grid[r][j] != CellState.UNKNOWN) rowKnown++;
}
for (int i = 0; i < board.rows; i++) {
if (board.grid[i][c] != CellState.UNKNOWN) colKnown++;
}
int score = -(rowKnown + colKnown); // 已知越多分数越低（越优先）
if (score < bestScore) {
bestScore = score;
bestR = r;
bestC = c;
}
}
}
return (bestR == -1) ? null : new int[]{bestR, bestC};
}
public int getBacktrackCount() { return backtrackCount; }
public int getGuessCount() { return guessCount; }
}
演示入口
package com.nonogram;
/**
* 数织求解器演示
*/
public class Main {
public static void main(String[] args) {
// 定义一个5x5的心形图案谜题
int[][] rowHints = {
{2, 2}, // ■■□■■
{5}, // ■■■■■
{3}, // □■■■□
{1}, // □□■□□
{1} // □□■□□
};
int[][] colHints = {
{2}, // ■■□□□
{3}, // ■■■□□
{5}, // ■■■■■
{3}, // ■■■□□
{2} // ■■□□□
};
NonogramBoard board = new NonogramBoard(5, 5, rowHints, colHints);
System.out.println("=== 数织求解器 ===\n");
System.out.println("初始状态：");
System.out.println(board);
NonogramSolver solver = new NonogramSolver();
long startTime = System.currentTimeMillis();
NonogramBoard solution = solver.solve(board);
long endTime = System.currentTimeMillis();
if (solution != null) {
System.out.println("\n求解成功！");
System.out.println(solution);
System.out.println("猜测次数：" + solver.getGuessCount());
System.out.println("回溯次数：" + solver.getBacktrackCount());
System.out.println("耗时：" + (endTime - startTime) + "ms");
} else {
System.out.println("\n该谜题无解！");
}
}
}
算法复杂度分析
单行求解复杂度
对于长度为 $L$、有 $k$ 个提示的一行，合法排列数上界为 $O\binom{L}{\sum hints}$。实际中约束传播会大幅减少搜索空间。
整体复杂度
- 约束传播：每轮 $O(N \times f(M) + M \times f(N))$，其中 $f(L)$ 是单行求解时间
- 回溯搜索：最坏 $O(2^{NM})$，但约束传播通常能将实际分支控制在可接受范围
- 对于常见的 $10 \times 10$ 到 $25 \times 25$ 谜题，通常秒级求解
优化策略
1. 增量求解
只重新计算发生变化的行/列，而非每轮全部重新求解。
2. 高级启发式
选择猜测位置时考虑：
– 该行/列提示的约束强度（提示数字越多越容易推理）
– 猜测后的传播效果（选择能引发最多传播的格子）
3. 对称性剪枝
利用行列对称性减少重复搜索。
总结
数织求解器是约束满足问题（CSP）的典型应用。通过将行列提示建模为约束、利用约束传播减少搜索空间、辅以回溯处理不确定性，我们构建了一个高效的自动求解器。这类技术在调度问题、配置设计、电路验证等领域都有广泛应用。
