引言
填字游戏（Crossword Puzzle）是一种广受欢迎的文字益智游戏，玩家需要根据线索提示，在纵横交错的网格中填入合适的单词。从算法角度看，填字游戏是一个典型的约束满足问题：横向单词与纵向单词在交叉位置必须共享相同的字母。本文用Java实现一个填字游戏自动求解器，核心算法包括字典树（Trie）高效前缀匹配与约束传播技术，让程序自动完成复杂的填字推理。
算法原理
交叉约束建模
将填字游戏网格中的每个连续空白序列视为一个变量（横向或纵向单词槽），每个槽需要填入一个长度匹配的单词。交叉位置形成约束：若横向槽的第 $i$ 个格子与纵向槽的第 $j$ 个格子重叠，则两单词在对应位置必须字母相同。
字典树前缀匹配
Trie树是一种高效的前缀匹配数据结构。在求解过程中，当我们确定某个槽的部分字母后（如通过交叉约束），可以迅速从Trie中筛选出所有匹配该前缀的候选单词，大幅缩减搜索空间。
约束传播（MRV启发式）
采用Minimum Remaining Values（MRV）策略：每次都选择候选单词最少的槽进行赋值。这样可以在搜索早期就发现矛盾，减少回溯次数。同时，每次赋值后立即向相邻槽传播约束，更新它们的候选集合。
Java实现
import java.util.*;
/**
* 填字游戏自动求解器：Trie前缀匹配 + 约束传播 + MRV回溯
*/
public class CrosswordSolver {
static class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isWord;
// 记录以该节点为前缀的所有单词，用于快速候选筛选
List<String> wordsWithPrefix = new ArrayList<>();
}
static class Trie {
TrieNode root = new TrieNode();
void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
}
node = node.children[idx];
node.wordsWithPrefix.add(word);
}
node.isWord = true;
}
// 获取匹配给定模式（如 "a__le"）的所有单词
List<String> matchPattern(String pattern) {
List<String> result = new ArrayList<>();
collectMatch(root, pattern, 0, new StringBuilder(), result);
return result;
}
void collectMatch(TrieNode node, String pattern, int pos,
StringBuilder sb, List<String> result) {
if (node == null) return;
if (pos == pattern.length()) {
if (node.isWord) result.add(sb.toString());
return;
}
char c = pattern.charAt(pos);
if (c == '_') {
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
sb.append((char) ('a' + i));
collectMatch(node.children[i], pattern, pos + 1, sb, result);
sb.deleteCharAt(sb.length() - 1);
}
}
} else {
int idx = c - 'a';
if (node.children[idx] != null) {
sb.append(c);
collectMatch(node.children[idx], pattern, pos + 1, sb, result);
sb.deleteCharAt(sb.length() - 1);
}
}
}
}
static class Slot {
int id, row, col, length;
boolean horizontal; // true=横向, false=纵向
// 交叉点：位置 -> 另一个slot的id及对应位置
Map<Integer, int[]> crosses = new HashMap<>();
String assigned = null;
Slot(int id, int r, int c, int len, boolean h) {
this.id = id; this.row = r; this.col = c;
this.length = len; this.horizontal = h;
}
// 根据当前交叉约束生成匹配模式
String getPattern(char[][] grid) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; i++) {
int r = horizontal ? row : row + i;
int c = horizontal ? col + i : col;
if (grid[r][c] == '_') sb.append('_');
else sb.append(grid[r][c]);
}
return sb.toString();
}
}
Trie trie;
List<Slot> slots;
char[][] grid;
int rows, cols;
public CrosswordSolver(Set<String> dictionary, int rows, int cols) {
this.trie = new Trie();
for (String w : dictionary) trie.insert(w.toLowerCase());
this.rows = rows; this.cols = cols;
this.grid = new char[rows][cols];
for (char[] row : grid) Arrays.fill(row, '#');
this.slots = new ArrayList<>();
}
/**
* 从网格中提取所有单词槽（横向和纵向连续空白）
*/
void extractSlots(boolean[][] open) {
int id = 0;
// 横向槽
for (int r = 0; r < rows; r++) {
int c = 0;
while (c < cols) {
while (c < cols && !open[r][c]) c++;
int start = c;
while (c < cols && open[r][c]) c++;
if (c - start >= 2) {
slots.add(new Slot(id++, r, start, c - start, true));
}
}
}
// 纵向槽
for (int c = 0; c < cols; c++) {
int r = 0;
while (r < rows) {
while (r < rows && !open[r][c]) r++;
int start = r;
while (r < rows && open[r][c]) r++;
if (r - start >= 2) {
slots.add(new Slot(id++, start, c, r - start, false));
}
}
}
// 建立交叉关系
for (Slot s1 : slots) {
for (Slot s2 : slots) {
if (s1.id >= s2.id) continue;
if (s1.horizontal == s2.horizontal) continue;
// 检查是否交叉
Slot h = s1.horizontal ? s1 : s2;
Slot v = s1.horizontal ? s2 : s1;
if (v.col >= h.col && v.col < h.col + h.length &&
h.row >= v.row && h.row < v.row + v.length) {
int hPos = v.col - h.col;
int vPos = h.row - v.row;
h.crosses.put(hPos, new int[]{v.id, vPos});
v.crosses.put(vPos, new int[]{h.id, hPos});
}
}
}
}
/**
* 使用MRV回溯 + 约束传播求解填字游戏
*/
public boolean solve() {
return backtrack(0);
}
boolean backtrack(int filled) {
if (filled == slots.size()) return true;
// MRV：选择候选最少的未填充槽
Slot bestSlot = null;
List<String> bestCandidates = null;
int minCandidates = Integer.MAX_VALUE;
for (Slot s : slots) {
if (s.assigned != null) continue;
String pattern = s.getPattern(grid);
List<String> candidates = trie.matchPattern(pattern);
// 额外过滤：确保与已赋值交叉槽一致
candidates.removeIf(word -> !consistent(s, word));
if (candidates.isEmpty()) return false; // 死路
if (candidates.size() < minCandidates) {
minCandidates = candidates.size();
bestSlot = s;
bestCandidates = candidates;
if (minCandidates == 1) break; // 无法更优
}
}
if (bestSlot == null) return false;
for (String word : bestCandidates) {
// 赋值
bestSlot.assigned = word;
fillGrid(bestSlot, word);
if (backtrack(filled + 1)) return true;
// 回溯
bestSlot.assigned = null;
unfillGrid(bestSlot);
}
return false;
}
boolean consistent(Slot s, String word) {
for (Map.Entry<Integer, int[]> entry : s.crosses.entrySet()) {
int pos = entry.getKey();
int[] other = entry.getValue();
Slot otherSlot = slots.get(other[0]);
int otherPos = other[1];
if (otherSlot.assigned != null) {
if (word.charAt(pos) != otherSlot.assigned.charAt(otherPos))
return false;
}
}
return true;
}
void fillGrid(Slot s, String word) {
for (int i = 0; i < s.length; i++) {
int r = s.horizontal ? s.row : s.row + i;
int c = s.horizontal ? s.col + i : s.col;
grid[r][c] = word.charAt(i);
}
}
void unfillGrid(Slot s) {
for (int i = 0; i < s.length; i++) {
int r = s.horizontal ? s.row : s.row + i;
int c = s.horizontal ? s.col + i : s.col;
// 只有不被其他已赋值槽覆盖的格子才清空
boolean covered = false;
for (Slot other : slots) {
if (other.id == s.id || other.assigned == null) continue;
if (other.horizontal) {
if (r == other.row && c >= other.col && c < other.col + other.length)
covered = true;
} else {
if (c == other.col && r >= other.row && r < other.row + other.length)
covered = true;
}
}
if (!covered) grid[r][c] = '_';
}
}
void printGrid() {
for (char[] row : grid) {
for (char c : row) {
System.out.print(c == '#' ? "# " : c + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
Set<String> dict = new HashSet<>(Arrays.asList(
"apple", "grape", "peach", "berry", "mango",
"april", "great", "peace", "beach", "magic",
"agent", "prize", "bread", "cream", "dream",
"eagle", "flame", "globe", "house", "image"
));
// 5x5网格，开放格子标记为true
boolean[][] open = {
{true, true, true, true, true},
{true, false, true, false, true},
{true, true, true, true, true},
{true, false, true, false, true},
{true, true, true, true, true}
};
CrosswordSolver solver = new CrosswordSolver(dict, 5, 5);
solver.extractSlots(open);
// 初始化开放格子为'_'
for (int r = 0; r < 5; r++)
for (int c = 0; c < 5; c++)
if (open[r][c]) solver.grid[r][c] = '_';
if (solver.solve()) {
System.out.println("填字游戏求解成功:");
solver.printGrid();
} else {
System.out.println("无解");
}
}
}
复杂度分析
- Trie构建：$O(W \times L)$，$W$ 为词典单词数，$L$ 为平均长度。
- 回溯搜索：最坏 $O(S! \times C^S)$，$S$ 为槽数量，$C$ 为平均候选数。MRV启发式和约束传播大幅剪枝，实际效率接近多项式级别。
- 模式匹配：单次 $O(26^K)$，$K$ 为未知字母数，但由于Trie剪枝通常远小于此。
总结
本文实现了填字游戏的自动求解器，核心创新在于将Trie前缀匹配与约束传播结合：Trie快速筛选候选单词，MRV策略决定搜索顺序，约束传播确保交叉位置的一致性。该框架可扩展至更大规模网格和更丰富的词典，甚至支持多解枚举与难度评估。
