引言
数织（Nonogram，又称Picross、逻辑绘画）是一种经典的逻辑解谜游戏。玩家根据每行每列给出的数字提示，在网格中填充色块，最终揭示出一幅隐藏图案。本文将用Java实现一个数织自动求解器，核心采用约束传播与回溯搜索两大算法。
问题建模
数织谜题可以形式化为约束满足问题（CSP）：
- 变量集合：网格中每个单元格的取值（0=空白，1=填充）
- 约束条件：每行/每列的填充块必须严格满足给定的连续段长度
例如，提示 [3, 2] 表示该行/列有两段连续的填充块，长度分别为3和2，段与段之间至少有一个空白间隔。
约束传播：行/列局部求解
约束传播的核心思想是：对于单行或单列，仅根据该行/列的提示，就能确定某些单元格必然为填充或必然为空白。
import java.util.*;
/**
* 数织求解器：约束传播 + 回溯搜索
*/
public class NonogramSolver {
// 单元格状态枚举
enum Cell {
UNKNOWN, // 未确定
FILLED, // 确定填充
EMPTY // 确定空白
}
private int rows, cols;
private Cell[][] grid; // 当前网格状态
private int[][] rowClues; // 行提示
private int[][] colClues; // 列提示
public NonogramSolver(int[][] rowClues, int[][] colClues) {
this.rows = rowClues.length;
this.cols = colClues.length;
this.rowClues = rowClues;
this.colClues = colClues;
this.grid = new Cell[rows][cols];
for (int i = 0; i < rows; i++) {
Arrays.fill(grid[i], Cell.UNKNOWN);
}
}
/**
* 约束传播：对单行/单列进行局部求解
* 使用"左对齐"和"右对齐"法确定必然单元格
* @param clues 该行/列的提示
* @param line 当前行/列的状态
* @return 是否有新单元格被确定
*/
public boolean propagateLine(int[] clues, Cell[] line) {
int n = line.length;
boolean changed = false;
// 计算最左可能放置位置
Cell[] leftmost = computeLeftmost(clues, line, n);
// 计算最右可能放置位置
Cell[] rightmost = computeRightmost(clues, line, n);
// 对于每个单元格：如果leftmost和rightmost都为FILLED，则必为FILLED
// 如果leftmost和rightmost在某位置矛盾（一个FILLED一个EMPTY），则利用约束
for (int i = 0; i < n; i++) {
if (line[i] != Cell.UNKNOWN) continue;
// 检查该位置在所有合法放置方案中是否始终一致
boolean alwaysFilled = true;
boolean alwaysEmpty = true;
// 生成所有与当前已知信息兼容的放置方案
List<Cell[]> candidates = generateValidPlacements(clues, line, n);
for (Cell[] cand : candidates) {
if (cand[i] == Cell.EMPTY) alwaysFilled = false;
if (cand[i] == Cell.FILLED) alwaysEmpty = false;
}
if (alwaysFilled && !alwaysEmpty && candidates.size() > 0) {
line[i] = Cell.FILLED;
changed = true;
} else if (alwaysEmpty && !alwaysFilled && candidates.size() > 0) {
line[i] = Cell.EMPTY;
changed = true;
}
}
return changed;
}
/**
* 生成所有与当前已知信息兼容的放置方案
* 使用递归回溯生成所有可能的填充模式
*/
private List<Cell[]> generateValidPlacements(int[] clues, Cell[] line, int n) {
List<Cell[]> results = new ArrayList<>();
Cell[] current = new Cell[n];
Arrays.fill(current, Cell.EMPTY);
backtrackPlacements(clues, 0, 0, line, current, results, n);
return results;
}
/**
* 递归生成放置方案
* @param clues 提示数组
* @param clueIdx 当前处理的提示索引
* @param startPos 当前提示可放置的起始位置
* @param line 当前行/列的已知状态（用于剪枝）
* @param current 当前构建的方案
* @param results 存储所有合法方案
*/
private void backtrackPlacements(int[] clues, int clueIdx, int startPos,
Cell[] line, Cell[] current,
List<Cell[]> results, int n) {
if (clueIdx == clues.length) {
// 所有提示已放置，检查剩余位置是否与已知信息冲突
for (int i = startPos; i < n; i++) {
if (line[i] == Cell.FILLED) return; // 剩余有未覆盖的FILLED，非法
}
results.add(current.clone());
return;
}
int blockLen = clues[clueIdx];
// 计算该提示块的最远可放置位置
int remainingSpace = 0;
for (int i = clueIdx + 1; i < clues.length; i++) {
remainingSpace += clues[i] + 1; // +1 for gap
}
int maxStart = n - remainingSpace - blockLen;
for (int pos = startPos; pos <= maxStart; pos++) {
// 检查从pos开始放置blockLen个FILLED是否与已知状态冲突
boolean conflict = false;
for (int i = pos; i < pos + blockLen; i++) {
if (line[i] == Cell.EMPTY) {
conflict = true;
break;
}
}
// 检查block后面的间隙位置（如果有的话）
if (!conflict && pos + blockLen < n && line[pos + blockLen] == Cell.FILLED) {
conflict = true;
}
// 检查pos前面的位置是否为FILLED（会导致块合并）
if (!conflict && pos > 0 && line[pos - 1] == Cell.FILLED) {
conflict = true;
}
if (conflict) {
// 如果当前位置不能放，但前面有UNKNOWN，可能还可以往后移
// 如果当前位置是FILLED，则必须从这里开始或之前，否则不可能
if (line[pos] == Cell.FILLED) break;
continue;
}
// 放置当前块
for (int i = pos; i < pos + blockLen; i++) {
current[i] = Cell.FILLED;
}
int nextStart = pos + blockLen + 1; // +1 for mandatory gap
backtrackPlacements(clues, clueIdx + 1, nextStart, line, current, results, n);
// 回溯：清空本次放置（恢复为EMPTY）
for (int i = pos; i < pos + blockLen; i++) {
current[i] = Cell.EMPTY;
}
}
}
/**
* 计算最左放置（简化版本，用于确定必然单元格）
*/
private Cell[] computeLeftmost(int[] clues, Cell[] line, int n) {
Cell[] result = new Cell[n];
Arrays.fill(result, Cell.EMPTY);
int pos = 0;
for (int clue : clues) {
while (pos < n && line[pos] == Cell.EMPTY) pos++;
for (int i = 0; i < clue && pos + i < n; i++) {
result[pos + i] = Cell.FILLED;
}
pos += clue + 1;
}
return result;
}
private Cell[] computeRightmost(int[] clues, Cell[] line, int n) {
Cell[] result = new Cell[n];
Arrays.fill(result, Cell.EMPTY);
int pos = n - 1;
for (int i = clues.length - 1; i >= 0; i--) {
int clue = clues[i];
while (pos >= 0 && line[pos] == Cell.EMPTY) pos--;
for (int j = 0; j < clue && pos - j >= 0; j++) {
result[pos - j] = Cell.FILLED;
}
pos -= clue + 1;
}
return result;
}
全局约束传播循环
/**
* 全局约束传播：交替对行和列进行传播，直到无法继续
* @return 是否有任何单元格被确定
*/
public boolean propagateAll() {
boolean anyChanged = false;
boolean changed;
do {
changed = false;
// 对所有行进行约束传播
for (int r = 0; r < rows; r++) {
if (propagateLine(rowClues[r], grid[r])) {
changed = true;
}
}
// 对所有列进行约束传播
for (int c = 0; c < cols; c++) {
Cell[] col = new Cell[rows];
for (int r = 0; r < rows; r++) col[r] = grid[r][c];
if (propagateLine(colClues[c], col)) {
// 将列的结果写回网格
for (int r = 0; r < rows; r++) {
if (grid[r][c] == Cell.UNKNOWN) {
grid[r][c] = col[r];
}
}
changed = true;
}
}
if (changed) anyChanged = true;
} while (changed);
return anyChanged;
}
回溯搜索求解
约束传播通常不足以完全求解复杂的数织谜题。当传播陷入停滞时，需要引入回溯搜索：选择一个UNKNOWN单元格，尝试两种赋值，递归求解。
/**
* 回溯搜索求解数织谜题
* @return 是否找到解
*/
public boolean solve() {
// 先进行约束传播
propagateAll();
// 检查是否已完全求解
if (isComplete()) {
return isValid();
}
// 选择分支变量（MRV启发式：选择约束最强的单元格）
int[] var = selectVariable();
if (var == null) return false;
int r = var[0], c = var[1];
// 尝试FILLED
Cell[][] backup = copyGrid();
grid[r][c] = Cell.FILLED;
if (solve()) return true;
// 回溯，尝试EMPTY
grid = backup;
backup = copyGrid();
grid[r][c] = Cell.EMPTY;
if (solve()) return true;
// 两种赋值都失败，回溯
grid = backup;
return false;
}
/**
* MRV启发式：选择剩余可能值最少的变量
* 简化实现：选择第一个UNKNOWN
*/
private int[] selectVariable() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == Cell.UNKNOWN) {
return new int[]{r, c};
}
}
}
return null;
}
private boolean isComplete() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == Cell.UNKNOWN) return false;
}
}
return true;
}
/**
* 验证当前网格是否满足所有约束
*/
private boolean isValid() {
for (int r = 0; r < rows; r++) {
if (!checkLine(rowClues[r], grid[r])) return false;
}
for (int c = 0; c < cols; c++) {
Cell[] col = new Cell[rows];
for (int r = 0; r < rows; r++) col[r] = grid[r][c];
if (!checkLine(colClues[c], col)) return false;
}
return true;
}
/**
* 检查单行/列是否满足提示约束
*/
private boolean checkLine(int[] clues, Cell[] line) {
List<Integer> runs = new ArrayList<>();
int count = 0;
for (Cell cell : line) {
if (cell == Cell.FILLED) {
count++;
} else {
if (count > 0) {
runs.add(count);
count = 0;
}
}
}
if (count > 0) runs.add(count);
if (runs.size() != clues.length) return false;
for (int i = 0; i < clues.length; i++) {
if (runs.get(i) != clues[i]) return false;
}
return true;
}
private Cell[][] copyGrid() {
Cell[][] copy = new Cell[rows][cols];
for (int i = 0; i < rows; i++) {
copy[i] = grid[i].clone();
}
return copy;
}
主程序与测试
/**
* 打印当前网格状态
*/
public void printGrid() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
char ch = grid[r][c] == Cell.FILLED ? '■' :
(grid[r][c] == Cell.EMPTY ? '·' : '?');
System.out.print(ch + " ");
}
System.out.print(" | ");
for (int clue : rowClues[r]) System.out.print(clue + " ");
System.out.println();
}
System.out.println("-".repeat(cols * 2));
for (int c = 0; c < cols; c++) {
for (int clue : colClues[c]) System.out.print(clue);
System.out.print(" ");
}
System.out.println();
}
public static void main(String[] args) {
// 测试用例：5x5的简单心形图案
int[][] rowClues = {
{1, 1},
{3},
{3},
{1},
{1}
};
int[][] colClues = {
{2},
{3},
{1},
{3},
{2}
};
NonogramSolver solver = new NonogramSolver(rowClues, colClues);
System.out.println("初始状态:");
solver.printGrid();
if (solver.solve()) {
System.out.println("\n求解成功!");
solver.printGrid();
} else {
System.out.println("\n无解");
}
}
}
算法复杂度分析
- 约束传播：每轮对 $R$ 行 $C$ 列各执行一次。单次行/列传播的复杂度为 $O(k \cdot 2^m)$，其中 $k$ 为提示数，$m$ 为长度。实际中通过大量剪枝，运行效率远高于理论上限
- 回溯搜索：最坏情况 $O(2^{R \cdot C})$，但约束传播极大剪枝了搜索空间。对于常规谜题（$< 25 \times 25$），可在毫秒到秒级求解
- 空间复杂度：$O(R \cdot C)$，存储网格状态
总结
本文实现了数织谜题的完整求解器，核心思想是：
- 约束传播：利用行/列的局部约束确定必然单元格，减少未知变量
- 回溯搜索：当传播停滞时，通过分支限界系统探索解空间
- MRV启发式：优先选择约束最强的变量分支，提高搜索效率
读者可以进一步扩展：实现更高级的线求解算法（如”Simple Spaces”、”Coloring”）、引入分布式约束传播、或构建图形界面交互式求解器。
