引言
数织（Nonogram）是一种源自日本的逻辑拼图游戏，玩家根据每行每列给出的数字提示，在网格中填充或留空，最终揭示出一幅隐藏图案。数织的求解本质上是一个约束满足问题（CSP），结合了约束传播与回溯搜索两大核心技术。本文将用Java实现一个完整的数织求解器，涵盖行/列约束解析、强制填充传播、以及带启发式的深度回溯。
游戏规则与数学建模
一个 $M \times N$ 的数织谜题，每行左侧和每列上方分别标注一组数字。例如行提示 [3, 1] 表示该行存在一段长度为3的连续填充块，随后至少间隔一个空格，再出现一段长度为1的填充块。
将数织形式化为CSP：
– 变量：网格中每个单元格的取值（填充/留空/未知）
– 约束：每行/每列必须精确满足给定的数字提示
– 搜索空间：理论上为 $2^{M \times N}$，实际通过约束传播大幅剪枝
核心算法一：行/列约束解析（Generate Line Possibilities）
对于单行长度为 $L$、提示为 $[a_1, a_2, …, a_k]$ 的情况，所有合法填充模式可通过递归生成。设总占用长度为 $\sum a_i + (k-1)$，剩余 $L – \text{占用}$ 个自由空格可在 $k+1$ 个间隙中分配。
import java.util.ArrayList;
import java.util.List;
/**
* 数织单行/单列的可能填充模式生成器
* 利用组合数学在间隙中分配剩余空格，枚举所有合法排列
*/
public class LineSolver {
/**
* 生成单行所有与当前已知状态兼容的填充模式
* @param length 行长度
* @param clues 数字提示，如 [3, 1]
* @param known 当前已知状态数组：1=填充, 0=留空, -1=未知
* @return 所有兼容的布尔模式列表，true表示填充
*/
public static List<boolean[]> generateCompatiblePatterns(int length, int[] clues, int[] known) {
List<boolean[]> result = new ArrayList<>();
// 计算提示总占用长度（含间隔）
int occupied = 0;
for (int c : clues) occupied += c;
occupied += Math.max(0, clues.length - 1); // 块间至少间隔1
int free = length - occupied; // 剩余可自由分配的空格
// 递归在 (clues.length + 1) 个间隙中分配 free 个空格
int[] gaps = new int[clues.length + 1];
backtrackGaps(result, gaps, 0, free, clues, length, known);
return result;
}
/**
* 递归分配间隙空格数
* @param result 结果收集器
* @param gaps 各间隙的空格数
* @param idx 当前处理第几个间隙
* @param remaining 剩余待分配空格数
* @param clues 数字提示
* @param length 行总长度
* @param known 当前已知状态
*/
private static void backtrackGaps(List<boolean[]> result, int[] gaps, int idx,
int remaining, int[] clues, int length, int[] known) {
if (idx == gaps.length) {
if (remaining == 0) {
boolean[] pattern = buildPattern(gaps, clues, length);
if (isCompatible(pattern, known)) {
result.add(pattern);
}
}
return;
}
// 第一个和最后一个间隙可以0空格，中间间隙至少1个（已在occupied中预留）
int max = remaining;
for (int i = 0; i <= max; i++) {
gaps[idx] = i;
backtrackGaps(result, gaps, idx + 1, remaining - i, clues, length, known);
}
}
/**
* 根据间隙和提示构建填充模式
*/
private static boolean[] buildPattern(int[] gaps, int[] clues, int length) {
boolean[] pattern = new boolean[length];
int pos = 0;
for (int i = 0; i < clues.length; i++) {
pos += gaps[i]; // 跳过前导空格
for (int j = 0; j < clues[i]; j++) {
pattern[pos++] = true; // 填充
}
if (i < clues.length - 1) {
pos++; // 块间强制间隔1格（已预留，这里直接跳过）
}
}
// 尾部空格由 gaps[last] 自然处理
return pattern;
}
/**
* 检查生成模式是否与当前已知状态冲突
*/
private static boolean isCompatible(boolean[] pattern, int[] known) {
for (int i = 0; i < known.length; i++) {
if (known[i] == 1 && !pattern[i]) return false; // 已知填充但模式留空
if (known[i] == 0 && pattern[i]) return false; // 已知留空但模式填充
}
return true;
}
}
核心算法二：约束传播（Intersection of Possibilities）
当一行存在多个兼容模式时，对所有模式取交集可确定必然填充或必然留空的单元格。若所有模式在某位置均为 true，则该位置强制填充；均为 false 则强制留空。
/**
* 约束传播核心：从所有兼容模式中推导必然状态
*/
public class ConstraintPropagator {
/**
* 对单行/单列执行约束传播
* @param patterns 所有兼容模式
* @param length 行长度
* @return 推导后的状态数组：1=强制填充, 0=强制留空, -1=仍未知
*/
public static int[] propagate(List<boolean[]> patterns, int length) {
if (patterns.isEmpty()) return null; // 无解
int[] result = new int[length];
for (int i = 0; i < length; i++) {
boolean allFill = true;
boolean allEmpty = true;
for (boolean[] p : patterns) {
if (!p[i]) allFill = false;
if (p[i]) allEmpty = false;
}
if (allFill) result[i] = 1;
else if (allEmpty) result[i] = 0;
else result[i] = -1;
}
return result;
}
}
核心算法三：带启发式的回溯搜索
约束传播往往无法完全求解复杂谜题，此时需引入回溯。启发式策略：优先选择可能性最少的行或列进行分支，以最大化剪枝效率。
import java.util.*;
/**
* 完整数织求解器：约束传播 + 启发式回溯
*/
public class NonogramSolver {
private final int rows, cols;
private final int[][] rowClues, colClues;
private int[][] grid; // 1=填充, 0=留空, -1=未知
private boolean solved = false;
public NonogramSolver(int[][] rowClues, int[][] colClues) {
this.rows = rowClues.length;
this.cols = colClues.length;
this.rowClues = rowClues;
this.colClues = colClues;
this.grid = new int[rows][cols];
for (int[] row : grid) Arrays.fill(row, -1);
}
/**
* 启动求解
* @return 若成功返回填充后的网格，否则返回null
*/
public int[][] solve() {
if (!propagateAll()) return null; // 初始传播发现矛盾
if (isComplete()) return grid;
backtrack();
return solved ? grid : null;
}
/**
* 对全部行和列进行循环约束传播，直到无法继续推导
* @return false表示发现矛盾（某行/列无兼容模式）
*/
private boolean propagateAll() {
boolean changed = true;
while (changed) {
changed = false;
for (int r = 0; r < rows; r++) {
int[] propagated = propagateLine(grid[r], rowClues[r], cols);
if (propagated == null) return false; // 矛盾
if (updateRow(r, propagated)) changed = true;
}
for (int c = 0; c < cols; c++) {
int[] col = extractColumn(c);
int[] propagated = propagateLine(col, colClues[c], rows);
if (propagated == null) return false;
if (updateCol(c, propagated)) changed = true;
}
}
return true;
}
/**
* 对单行/单列执行约束传播
*/
private int[] propagateLine(int[] known, int[] clues, int length) {
List<boolean[]> patterns = LineSolver.generateCompatiblePatterns(length, clues, known);
return ConstraintPropagator.propagate(patterns, length);
}
private int[] extractColumn(int c) {
int[] col = new int[rows];
for (int r = 0; r < rows; r++) col[r] = grid[r][c];
return col;
}
private boolean updateRow(int r, int[] propagated) {
boolean changed = false;
for (int c = 0; c < cols; c++) {
if (grid[r][c] == -1 && propagated[c] != -1) {
grid[r][c] = propagated[c];
changed = true;
}
}
return changed;
}
private boolean updateCol(int c, int[] propagated) {
boolean changed = false;
for (int r = 0; r < rows; r++) {
if (grid[r][c] == -1 && propagated[r] != -1) {
grid[r][c] = propagated[r];
changed = true;
}
}
return changed;
}
private boolean isComplete() {
for (int[] row : grid) {
for (int v : row) if (v == -1) return false;
}
return true;
}
/**
* 启发式回溯：选择可能性最少的未知单元格进行分支
*/
private void backtrack() {
if (solved) return;
if (isComplete()) { solved = true; return; }
// 找到可能性最少的行或列（简化：直接找第一个未知格子）
int[] pos = findMostConstrainedCell();
if (pos == null) return;
int r = pos[0], c = pos[1];
// 分支1：尝试填充
int[][] backup = deepCopy(grid);
grid[r][c] = 1;
if (propagateAll()) {
backtrack();
if (solved) return;
}
// 分支2：尝试留空
grid = backup;
grid[r][c] = 0;
if (propagateAll()) {
backtrack();
if (solved) return;
}
grid = backup; // 回溯恢复
}
private int[] findMostConstrainedCell() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == -1) return new int[]{r, c};
}
}
return null;
}
private int[][] deepCopy(int[][] src) {
int[][] dst = new int[src.length][];
for (int i = 0; i < src.length; i++) dst[i] = src[i].clone();
return dst;
}
/**
* 打印求解结果
*/
public void printSolution() {
for (int[] row : grid) {
for (int v : row) {
System.out.print(v == 1 ? "██" : " ");
}
System.out.println();
}
}
// 测试主函数
public static void main(String[] args) {
// 5x5 心形图案谜题
int[][] rowClues = {{2, 2}, {5}, {1, 1, 1}, {1, 1}, {2}};
int[][] colClues = {{3}, {2, 1}, {1, 1, 1}, {2, 1}, {3}};
NonogramSolver solver = new NonogramSolver(rowClues, colClues);
int[][] solution = solver.solve();
if (solution != null) {
System.out.println("求解成功：");
solver.printSolution();
} else {
System.out.println("无解");
}
}
}
复杂度分析
| 阶段 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 模式生成 | $O(C(L, k))$ | $O(P \cdot L)$ | $P$ 为兼容模式数，$k$ 为提示块数 |
| 约束传播 | $O((R+C) \cdot P \cdot L)$ | $O(R \cdot C)$ | 每轮扫描所有行列 |
| 回溯搜索 | 最坏 $O(2^{R \cdot C})$ | $O(R \cdot C)$ | 实际剪枝后接近多项式级 |
扩展方向
- 高级启发式：使用MRV（最小剩余值）选择分支变量，或按行/列可能性数排序
- 双向传播：同时从行和列方向进行约束传播，增强推导力度
- 图形界面：结合JavaFX或Swing实现可视化交互式求解器
- 谜题生成：通过随机图案反向生成唯一解的数织谜题
总结
数织求解完美展示了约束满足问题的经典范式：先用约束传播快速确定必然状态，缩小搜索空间；再通过启发式回溯处理剩余不确定性。这种”传播+搜索”的组合策略也是数独、扫雷等逻辑游戏求解器的核心架构。
