引言
纵横字谜（Crossword Puzzle）是报纸和杂志上最常见的益智游戏之一。玩家需要根据提示，在一个由黑白格组成的网格中填入单词，使得横向和纵向的单词都符合对应的线索。对于程序而言，这本质上是一个约束满足问题（Constraint Satisfaction Problem, CSP）。
本文将用Java实现一个完整的纵横字谜自动求解器，通过回溯搜索结合约束传播技术，高效地填充字谜网格。算法核心借鉴了人工智能领域中经典的CSP求解框架，包括变量排序、值排序、前向检查等优化策略。
问题建模为CSP
变量（Variables）
字谜网格中的每个空白序列（横向或纵向的连续白格）就是一个变量。每个变量有：
– 位置：起始坐标和方向（横/纵）
– 长度：空白格的数量
– 域（Domain）：所有长度匹配且符合当前约束的候选单词
约束（Constraints）
- 交叉约束：两个变量相交的格子必须填入相同的字母
- 唯一性约束（可选）：同一个单词不能重复使用
- 线索约束：某些位置可能有预设的字母（如固定提示）
核心算法设计
1. 网格解析
将二维字符网格解析为变量集合。例如：
# # # # #
# _ _ _ #
# _ # _ #
# _ _ _ #
# # # # #
解析出：
– 横向变量：(1,1)向右长度3，(3,1)向右长度3
– 纵向变量：(1,1)向下长度3，(1,2)向下长度1，(1,3)向下长度3
2. 回溯搜索
function Backtrack(assignment):
if assignment is complete: return assignment
var = SelectUnassignedVariable()
for value in OrderDomainValues(var):
if value is consistent with assignment:
add {var = value} to assignment
inferences = ForwardCheck(var, value)
if inferences != failure:
add inferences to assignment
result = Backtrack(assignment)
if result != failure: return result
remove inferences from assignment
remove {var = value} from assignment
return failure
3. 约束传播：前向检查
每当一个变量被赋值后，立即检查所有与之相邻的未赋值变量，从它们的域中移除因交叉约束而变得不可能的取值。如果某个变量的域为空，则立即回溯。
Java实现
import java.util.*;
/**
* 纵横字谜自动求解器
* 使用回溯搜索 + 约束传播（前向检查）求解CSP问题
*/
public class CrosswordSolver {
// 网格中黑格用'#'表示，白格用'_'表示，已填字母直接写
private char[][] grid;
private final int rows;
private final int cols;
// 候选词库：按长度分组存储
private final Map<Integer, List<String>> wordDict;
// 解析出的所有变量（空白序列）
private List<Variable> variables;
// 变量之间的交叉约束关系
private Map<Variable, List<Constraint>> constraints;
/**
* 表示字谜中的一个变量（横向或纵向的连续白格序列）
*/
static class Variable {
final int row; // 起始行
final int col; // 起始列
final int length; // 长度
final boolean horizontal; // true=横向, false=纵向
final String id; // 唯一标识
List<String> domain; // 候选单词域
String assignedValue; // 当前赋值（null表示未赋值）
public Variable(int row, int col, int length, boolean horizontal) {
this.row = row;
this.col = col;
this.length = length;
this.horizontal = horizontal;
this.id = (horizontal ? "H" : "V") + "_" + row + "_" + col;
this.domain = new ArrayList<>();
this.assignedValue = null;
}
/**
* 获取该变量第idx个格子的全局坐标
*/
public int[] getCellPosition(int idx) {
if (horizontal) {
return new int[]{row, col + idx};
} else {
return new int[]{row + idx, col};
}
}
@Override
public String toString() {
return id + "(len=" + length + ")";
}
}
/**
* 表示两个变量之间的交叉约束
*/
static class Constraint {
final Variable var1;
final Variable var2;
final int pos1; // var1中交叉的位置
final int pos2; // var2中交叉的位置
public Constraint(Variable var1, int pos1, Variable var2, int pos2) {
this.var1 = var1;
this.pos1 = pos1;
this.var2 = var2;
this.pos2 = pos2;
}
/**
* 检查两个赋值是否满足交叉约束（对应位置字母相同）
*/
public boolean isSatisfied(String val1, String val2) {
if (val1 == null || val2 == null) return true;
return val1.charAt(pos1) == val2.charAt(pos2);
}
}
public CrosswordSolver(char[][] grid, List<String> words) {
this.grid = new char[grid.length][];
for (int i = 0; i < grid.length; i++) {
this.grid[i] = grid[i].clone();
}
this.rows = grid.length;
this.cols = grid[0].length;
// 按长度组织词库
this.wordDict = new HashMap<>();
for (String word : words) {
wordDict.computeIfAbsent(word.length(), k -> new ArrayList<>()).add(word);
}
// 解析变量和约束
parseVariables();
buildConstraints();
initializeDomains();
}
/**
* 解析网格中的所有变量（连续白格序列）
*/
private void parseVariables() {
variables = new ArrayList<>();
// 解析横向变量
for (int r = 0; r < rows; r++) {
int c = 0;
while (c < cols) {
// 跳过黑格
if (grid[r][c] == '#') {
c++;
continue;
}
// 找到连续白格的起始
int start = c;
while (c < cols && grid[r][c] != '#') {
c++;
}
int length = c - start;
if (length >= 2) { // 至少2格才构成有效单词位置
variables.add(new Variable(r, start, length, true));
}
}
}
// 解析纵向变量
for (int c = 0; c < cols; c++) {
int r = 0;
while (r < rows) {
if (grid[r][c] == '#') {
r++;
continue;
}
int start = r;
while (r < rows && grid[r][c] != '#') {
r++;
}
int length = r - start;
if (length >= 2) {
variables.add(new Variable(start, c, length, false));
}
}
}
System.out.println("解析出 " + variables.size() + " 个变量");
}
/**
* 构建变量之间的交叉约束
*/
private void buildConstraints() {
constraints = new HashMap<>();
for (Variable v : variables) {
constraints.put(v, new ArrayList<>());
}
// 检查每对变量是否有交叉
for (int i = 0; i < variables.size(); i++) {
for (int j = i + 1; j < variables.size(); j++) {
Variable v1 = variables.get(i);
Variable v2 = variables.get(j);
// 同方向不可能交叉
if (v1.horizontal == v2.horizontal) continue;
// 找到交叉点
Variable hVar = v1.horizontal ? v1 : v2;
Variable vVar = v1.horizontal ? v2 : v1;
// 横向变量的行必须在纵向变量的列范围内
// 纵向变量的列必须在横向变量的行范围内
if (hVar.row >= vVar.row && hVar.row < vVar.row + vVar.length
&& vVar.col >= hVar.col && vVar.col < hVar.col + hVar.length) {
int hPos = vVar.col - hVar.col;
int vPos = hVar.row - vVar.row;
Constraint c1 = new Constraint(hVar, hPos, vVar, vPos);
Constraint c2 = new Constraint(vVar, vPos, hVar, hPos);
constraints.get(hVar).add(c1);
constraints.get(vVar).add(c2);
}
}
}
}
/**
* 初始化每个变量的域（候选单词）
* 同时考虑网格中已有的预设字母
*/
private void initializeDomains() {
for (Variable v : variables) {
List<String> candidates = wordDict.getOrDefault(v.length, new ArrayList<>());
v.domain = new ArrayList<>();
for (String word : candidates) {
if (matchesGridConstraints(v, word)) {
v.domain.add(word);
}
}
}
}
/**
* 检查单词是否符合网格中的预设字母约束
*/
private boolean matchesGridConstraints(Variable v, String word) {
for (int i = 0; i < v.length; i++) {
int[] pos = v.getCellPosition(i);
char gridChar = grid[pos[0]][pos[1]];
if (gridChar != '_' && gridChar != word.charAt(i)) {
return false;
}
}
return true;
}
/**
* MRV启发式：选择域最小的未赋值变量
* （Minimum Remaining Values）
*/
private Variable selectMRVVariable() {
Variable best = null;
int minDomainSize = Integer.MAX_VALUE;
for (Variable v : variables) {
if (v.assignedValue == null && v.domain.size() < minDomainSize) {
minDomainSize = v.domain.size();
best = v;
}
}
return best;
}
/**
* 度启发式：选择约束最多的未赋值变量（MRV相同时的打破平局策略）
*/
private Variable selectDegreeVariable() {
Variable best = null;
int maxDegree = -1;
for (Variable v : variables) {
if (v.assignedValue == null) {
int degree = constraints.get(v).size();
if (degree > maxDegree) {
maxDegree = degree;
best = v;
}
}
}
return best;
}
/**
* 综合选择策略：优先MRV，平局时选度最大的
*/
private Variable selectVariable() {
Variable mrv = selectMRVVariable();
if (mrv == null) return null;
// 检查是否有多个变量具有相同的最小域大小
int minSize = mrv.domain.size();
List<Variable> ties = new ArrayList<>();
for (Variable v : variables) {
if (v.assignedValue == null && v.domain.size() == minSize) {
ties.add(v);
}
}
if (ties.size() == 1) return mrv;
// 平局时用度启发式
Variable best = ties.get(0);
int maxDegree = constraints.get(best).size();
for (int i = 1; i < ties.size(); i++) {
int degree = constraints.get(ties.get(i)).size();
if (degree > maxDegree) {
maxDegree = degree;
best = ties.get(i);
}
}
return best;
}
/**
* 前向检查：赋值后更新相关变量的域
* @return 如果某个变量域为空则返回null（失败）
*/
private Map<Variable, List<String>> forwardCheck(Variable var, String value) {
Map<Variable, List<String>> removed = new HashMap<>();
for (Constraint c : constraints.get(var)) {
Variable other = (c.var1 == var) ? c.var2 : c.var1;
if (other.assignedValue != null) continue;
List<String> toRemove = new ArrayList<>();
for (String candidate : other.domain) {
if (!c.isSatisfied(value, candidate)) {
toRemove.add(candidate);
}
}
if (!toRemove.isEmpty()) {
other.domain.removeAll(toRemove);
removed.put(other, toRemove);
// 如果域为空，约束传播失败
if (other.domain.isEmpty()) {
// 恢复已移除的值
for (Map.Entry<Variable, List<String>> entry : removed.entrySet()) {
entry.getKey().domain.addAll(entry.getValue());
}
return null;
}
}
}
return removed;
}
/**
* 恢复前向检查移除的域值
*/
private void undoForwardCheck(Map<Variable, List<String>> removed) {
if (removed == null) return;
for (Map.Entry<Variable, List<String>> entry : removed.entrySet()) {
entry.getKey().domain.addAll(entry.getValue());
// 去重（安全处理）
Set<String> unique = new HashSet<>(entry.getKey().domain);
entry.getKey().domain.clear();
entry.getKey().domain.addAll(unique);
}
}
/**
* 检查当前赋值是否满足所有约束
*/
private boolean isConsistent() {
for (Variable v : variables) {
if (v.assignedValue == null) continue;
for (Constraint c : constraints.get(v)) {
Variable other = (c.var1 == v) ? c.var2 : c.var1;
if (other.assignedValue != null) {
if (!c.isSatisfied(v.assignedValue, other.assignedValue)) {
return false;
}
}
}
}
return true;
}
/**
* 核心回溯搜索算法
*/
public boolean solve() {
return backtrack();
}
private boolean backtrack() {
// 检查是否所有变量都已赋值
boolean allAssigned = true;
for (Variable v : variables) {
if (v.assignedValue == null) {
allAssigned = false;
break;
}
}
if (allAssigned) return isConsistent();
// 选择下一个变量（MRV + Degree启发式）
Variable var = selectVariable();
if (var == null) return true;
// 按最少约束值（LCV）排序候选值
List<String> orderedValues = orderByLCV(var);
for (String value : orderedValues) {
// 赋值
var.assignedValue = value;
// 前向检查
Map<Variable, List<String>> removed = forwardCheck(var, value);
if (removed != null) {
// 递归搜索
if (backtrack()) {
return true;
}
// 回溯：恢复域
undoForwardCheck(removed);
}
// 撤销赋值
var.assignedValue = null;
}
return false;
}
/**
* LCV启发式：优先选择对其他变量约束最少的值
* （Least Constraining Value）
*/
private List<String> orderByLCV(Variable var) {
List<Map.Entry<String, Integer>> scored = new ArrayList<>();
for (String value : var.domain) {
int constraintsCount = 0;
for (Constraint c : constraints.get(var)) {
Variable other = (c.var1 == var) ? c.var2 : c.var1;
if (other.assignedValue != null) continue;
for (String otherVal : other.domain) {
if (!c.isSatisfied(value, otherVal)) {
constraintsCount++;
}
}
}
scored.add(new AbstractMap.SimpleEntry<>(value, constraintsCount));
}
scored.sort(Comparator.comparingInt(Map.Entry::getValue));
List<String> result = new ArrayList<>();
for (Map.Entry<String, Integer> e : scored) {
result.add(e.getKey());
}
return result;
}
/**
* 将求解结果填入网格并打印
*/
public void printSolution() {
char[][] result = new char[rows][cols];
for (int r = 0; r < rows; r++) {
result[r] = grid[r].clone();
}
for (Variable v : variables) {
if (v.assignedValue != null) {
for (int i = 0; i < v.length; i++) {
int[] pos = v.getCellPosition(i);
result[pos[0]][pos[1]] = v.assignedValue.charAt(i);
}
}
}
System.out.println("\n=== 字谜解答 ===");
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
System.out.print(result[r][c] + " ");
}
System.out.println();
}
}
/**
* 主程序：演示求解过程
*/
public static void main(String[] args) {
// 简单的5x5字谜网格
char[][] grid = {
{'#', '#', '#', '#', '#'},
{'#', '_', '_', '_', '#'},
{'#', '_', '#', '_', '#'},
{'#', '_', '_', '_', '#'},
{'#', '#', '#', '#', '#'}
};
// 候选词库（横向/纵向单词）
List<String> words = Arrays.asList(
"CAT", "BAT", "RAT", "HAT", "MAT",
"CAR", "BAR", "ART", "ACT", "CAT",
"CAB", "TAB", "TAR", "RAT"
);
CrosswordSolver solver = new CrosswordSolver(grid, words);
System.out.println("开始求解纵横字谜...");
boolean success = solver.solve();
if (success) {
System.out.println("求解成功！");
solver.printSolution();
// 打印每个变量的赋值
System.out.println("\n变量赋值详情：");
for (Variable v : solver.variables) {
System.out.println(v + " = " + v.assignedValue);
}
} else {
System.out.println("无解！请检查网格和词库。");
}
}
}
复杂度分析
- 变量数量：设网格为
R × C，变量数量约为O(R × C)（每个格子可能属于两个变量）。 - 域大小：每个变量的候选词数量，取决于词库大小，记为
D。 - 搜索空间最坏情况：
O(D^V)，其中V是变量数量。 - MRV + 前向检查的实际效果：通过约束传播大幅剪枝，实际运行时间通常远低于理论最坏情况。对于典型报纸字谜（10×10网格，变量约30个），可在秒级求解。
- 空间复杂度：
O(V × D)存储变量域和约束关系。
算法优化策略
- MRV（最小剩余值）：优先处理选择最少的变量，能最快发现矛盾并回溯。
- 度启发式：当MRV平局时，选择约束最多的变量，因为它对未来分支的影响最大。
- LCV（最少约束值）：优先尝试对其他变量影响最小的候选值，保留更多后续选择空间。
- AC-3（弧一致性）：比前向检查更强的约束传播，可以进一步缩减搜索空间。
- 字典树（Trie）优化：将词库存储为Trie结构，在交叉约束检查时可快速过滤不满足前缀约束的单词。
现实应用扩展
纵横字谜求解器的核心CSP框架广泛应用于：
– 数独求解：9×9网格，每行/列/宫为约束
– 课程表排课：教师、教室、时间为变量，冲突为约束
– 电路板布局：元件位置为变量，间距为约束
– 密码破解：字符位置为变量，字典和模式为约束
总结
纵横字谜自动求解是约束满足问题的教科书级案例。通过将游戏规则精确建模为CSP，并运用MRV、度启发式、LCV和前向检查等经典优化策略，我们能够在可接受的时间内求解复杂的字谜问题。
这个算法的核心启示是：约束即信息。每填一个字母，就传播到所有相交的单词，逐步缩小搜索空间。在现实生活中，无论是排课、调度还是资源分配，善于发现和利用约束，往往能让看似无解的问题迎刃而解。
