引言
Crossword（填字游戏）是报纸和杂志中广受欢迎的文字谜题，玩家根据提示在交叉的横纵格子中填入单词。自动生成交叉字谜是经典的约束满足问题（CSP）。本文用Java实现Crossword生成器，核心讲解两个算法：一是通过回溯搜索（Backtracking Search）尝试填入候选单词，二是利用前向检查（Forward Checking）与约束传播（Constraint Propagation）提前剪枝无效分支。
核心算法设计
1. 问题建模为CSP
将Crossword建模为约束满足问题：
– 变量：每个待填的横向或纵向词槽（Slot）
– 值域：每个词槽可用的候选单词列表
– 约束：相交的两个词槽在交叉位置字符必须相同
2. 回溯搜索 + MRV启发式
采用最少剩余值（Minimum Remaining Values, MRV）启发式优先选择约束最紧的变量，减少分支因子。每次赋值后通过前向检查更新相邻变量的值域，若某变量值域为空则立即回溯。
3. 约束传播（AC-3）
维护一个弧队列，对每对相交的词槽检查一致性：若某个字符位置无对应单词匹配，则从值域中移除该单词。反复传播直到队列为空或发现空值域。
完整Java实现
import java.util.*;
/**
* Crossword 生成器：回溯搜索 + 约束传播
*/
public class CrosswordGenerator {
int rows, cols;
char[][] grid; // '#'为黑格，'_'为待填，字母为已填
List<Slot> slots; // 所有词槽
Set<String> dictionary; // 词典
public CrosswordGenerator(int rows, int cols, char[][] pattern, Set<String> dict) {
this.rows = rows; this.cols = cols;
this.grid = new char[rows][cols];
for (int i=0;i<rows;i++) System.arraycopy(pattern[i], 0, grid[i], 0, cols);
this.dictionary = dict;
this.slots = extractSlots();
}
/**
* 从网格中提取所有横向和纵向词槽
*/
List<Slot> extractSlots() {
List<Slot> result = new ArrayList<>();
// 横向词槽
for (int r=0; r<rows; r++) {
int c=0;
while (c<cols) {
while (c<cols && grid[r][c]=='#') c++;
int start=c;
while (c<cols && grid[r][c]!='#') c++;
if (c-start >= 2) result.add(new Slot(r, start, r, c-1, true));
}
}
// 纵向词槽
for (int c=0; c<cols; c++) {
int r=0;
while (r<rows) {
while (r<rows && grid[r][c]=='#') r++;
int start=r;
while (r<rows && grid[r][c]!='#') r++;
if (r-start >= 2) result.add(new Slot(start, c, r-1, c, false));
}
}
return result;
}
/**
* 词槽类：记录位置和相交关系
*/
class Slot {
int r1, c1, r2, c2;
boolean horizontal;
int length;
List<String> domain; // 候选单词
List<Intersection> intersects; // 相交的词槽
String assigned = null; // 当前赋值
Slot(int r1, int c1, int r2, int c2, boolean h) {
this.r1=r1; this.c1=c1; this.r2=r2; this.c2=c2; this.horizontal=h;
this.length = h ? (c2-c1+1) : (r2-r1+1);
this.intersects = new ArrayList<>();
initDomain();
}
void initDomain() {
domain = new ArrayList<>();
for (String w : dictionary) {
if (w.length() == length) domain.add(w);
}
}
/** 获取词槽中指定偏移位置的字符 */
char getCharAt(int offset) {
if (assigned != null) return assigned.charAt(offset);
int r = horizontal ? r1 : r1+offset;
int c = horizontal ? c1+offset : c1;
return grid[r][c] == '_' ? '?' : grid[r][c];
}
void setAssigned(String word) { this.assigned = word; }
void clearAssigned() { this.assigned = null; }
}
/**
* 相交关系：记录两个词槽的交叉位置
*/
class Intersection {
Slot other;
int thisOffset; // 在本词槽中的偏移
int otherOffset; // 在对方词槽中的偏移
Intersection(Slot o, int to, int oo) { other=o; thisOffset=to; otherOffset=oo; }
}
/**
* 构建相交关系图
*/
void buildIntersections() {
for (int i=0; i<slots.size(); i++) {
for (int j=i+1; j<slots.size(); j++) {
Slot a = slots.get(i), b = slots.get(j);
// 检查是否相交（一个横向一个纵向）
if (a.horizontal == b.horizontal) continue;
Slot h = a.horizontal ? a : b;
Slot v = a.horizontal ? b : a;
// 纵向词槽的列是否在横向词槽范围内，且横向词槽的行是否在纵向词槽范围内
if (v.c1 >= h.c1 && v.c1 <= h.c2 && h.r1 >= v.r1 && h.r1 <= v.r2) {
int hOffset = v.c1 - h.c1;
int vOffset = h.r1 - v.r1;
h.intersects.add(new Intersection(v, hOffset, vOffset));
v.intersects.add(new Intersection(h, vOffset, hOffset));
}
}
}
}
/**
* 主求解入口：带MRV启发式的回溯搜索
*/
boolean solve() {
buildIntersections();
return backtrack(0);
}
/**
* 回溯搜索：每次选择MRV变量
*/
boolean backtrack(int depth) {
// 检查是否全部赋值
boolean allAssigned = true;
for (Slot s : slots) if (s.assigned == null) { allAssigned = false; break; }
if (allAssigned) return true;
// MRV：选择值域最小的未赋值变量
Slot var = selectMRV();
if (var == null || var.domain.isEmpty()) return false;
// 按约束度排序候选值（优先选择约束更强的值）
List<String> ordered = orderDomainValues(var);
for (String word : ordered) {
if (!isConsistent(var, word)) continue;
// 赋值
var.setAssigned(word);
updateGrid(var);
// 前向检查：保存相邻变量值域状态
Map<Slot, List<String>> savedDomains = forwardCheck(var);
if (savedDomains != null) { // 无空值域，继续搜索
if (backtrack(depth+1)) return true;
}
// 回溯：恢复状态
restoreDomains(savedDomains);
var.clearAssigned();
restoreGrid(var);
}
return false;
}
/** MRV启发式：选择值域最小的未赋值变量 */
Slot selectMRV() {
Slot best = null;
int minDomain = Integer.MAX_VALUE;
for (Slot s : slots) {
if (s.assigned != null) continue;
int d = s.domain.size();
if (d < minDomain) { minDomain = d; best = s; }
}
return best;
}
/** 检查单词与当前已填约束是否一致 */
boolean isConsistent(Slot slot, String word) {
for (int i=0; i<slot.length; i++) {
char existing = slot.getCharAt(i);
if (existing != '?' && existing != word.charAt(i)) return false;
}
// 检查与已赋值相交词槽的交叉约束
for (Intersection inter : slot.intersects) {
Slot other = inter.other;
if (other.assigned != null) {
if (word.charAt(inter.thisOffset) != other.assigned.charAt(inter.otherOffset))
return false;
}
}
return true;
}
/** 前向检查：根据新赋值过滤相邻未赋值变量的值域 */
Map<Slot, List<String>> forwardCheck(Slot assignedSlot) {
Map<Slot, List<String>> saved = new HashMap<>();
for (Intersection inter : assignedSlot.intersects) {
Slot neighbor = inter.other;
if (neighbor.assigned != null) continue;
char requiredChar = assignedSlot.assigned.charAt(inter.thisOffset);
List<String> original = new ArrayList<>(neighbor.domain);
saved.put(neighbor, original);
// 过滤值域：只保留交叉位置字符匹配的词
neighbor.domain.removeIf(w -> w.charAt(inter.otherOffset) != requiredChar);
if (neighbor.domain.isEmpty()) {
// 恢复并返回失败
for (Map.Entry<Slot, List<String>> e : saved.entrySet()) {
e.getKey().domain = e.getValue();
}
return null;
}
}
return saved;
}
void restoreDomains(Map<Slot, List<String>> saved) {
if (saved == null) return;
for (Map.Entry<Slot, List<String>> e : saved.entrySet()) {
e.getKey().domain = e.getValue();
}
}
/** 按对邻居的约束程度排序候选值 */
List<String> orderDomainValues(Slot slot) {
List<String> copy = new ArrayList<>(slot.domain);
copy.sort((a, b) -> {
int ca = countConstraining(a, slot), cb = countConstraining(b, slot);
return Integer.compare(ca, cb); // 约束多的优先（更可能减少分支）
});
return copy;
}
int countConstraining(String word, Slot slot) {
int count = 0;
for (Intersection inter : slot.intersects) {
Slot other = inter.other;
if (other.assigned != null) continue;
char c = word.charAt(inter.thisOffset);
for (String w : other.domain) {
if (w.charAt(inter.otherOffset) == c) count++;
}
}
return count;
}
void updateGrid(Slot s) {
for (int i=0; i<s.length; i++) {
int r = s.horizontal ? s.r1 : s.r1+i;
int c = s.horizontal ? s.c1+i : s.c1;
grid[r][c] = s.assigned.charAt(i);
}
}
void restoreGrid(Slot s) {
for (int i=0; i<s.length; i++) {
int r = s.horizontal ? s.r1 : s.r1+i;
int c = s.horizontal ? s.c1+i : s.c1;
// 检查是否被其他已赋值词槽覆盖
boolean covered = false;
for (Slot other : slots) {
if (other != s && other.assigned != null && otherCovers(other, r, c)) {
covered = true; break;
}
}
if (!covered) grid[r][c] = '_';
}
}
boolean otherCovers(Slot s, int r, int c) {
if (s.horizontal) return s.r1 == r && c >= s.c1 && c <= s.c2;
return s.c1 == c && r >= s.r1 && r <= s.r2;
}
void printGrid() {
for (char[] row : grid) {
for (char c : row) System.out.print(c == '#' ? "## " : String.format("%2c ", c));
System.out.println();
}
}
public static void main(String[] args) {
// 5x5 简单交叉字谜模板：#为黑格，_为白格
char[][] pattern = {
{'#','_','_','_','#'},
{'_','_','_','_','_'},
{'_','_','#','_','_'},
{'_','_','_','_','_'},
{'#','_','_','_','#'}
};
Set<String> dict = new HashSet<>(Arrays.asList(
"HELLO", "WORLD", "ALGORITHM", "JAVA", "CODE",
"HELLO", "LODGE", "GROWN", "OWNED", "WOOER",
"HEART", "EARTH", "WATER", "FIRES", "WINDY",
"APPLE", "GRAPE", "PEACH", "MELON", "BERRY",
"PIZZA", "PASTA", "SUSHI", "TACOS", "SALAD"
));
CrosswordGenerator gen = new CrosswordGenerator(5, 5, pattern, dict);
if (gen.solve()) {
System.out.println("Crossword 生成成功！");
gen.printGrid();
} else {
System.out.println("无解，请扩展词典或修改模板。");
}
}
}
复杂度分析
- 词槽提取：扫描整个网格两次（横纵），时间
O(RC)，空间O(S)，S为词槽数。 - 回溯搜索：最坏情况
O(D^S)，D为平均词域大小，S为词槽数。MRV启发式将实际分支因子大幅降低。 - 前向检查：每次赋值后检查所有相交词槽，时间
O(S × D × L)，L为词长。但能有效剪枝，总体搜索空间远小于纯回溯。
总结
本文将Crossword生成建模为约束满足问题，实现了MRV启发式回溯搜索配合前向检查。读者可以进一步引入AC-3算法实现更强的弧一致性约束传播，或扩展词典和模板生成更复杂的交叉字谜。该框架也适用于数独、填字等其他CSP问题。
