引言
Str8ts 是一种由纽约时报填字游戏编辑发明的数字逻辑谜题，规则类似于数独但增加了”连续序列”的约束：在每一行和每一列中，被黑色格子分隔开的白色区间内的数字必须构成连续递增或递减的序列（如 2-3-4-5 或 7-6-5）。本文将用 Java 实现一个 Str8ts 求解器，核心采用候选数排除（Candidate Elimination）与唯一解策略（Naked Singles & Hidden Singles）。
核心算法思路
1. 问题建模
Str8ts 棋盘由 n×n 格子组成，部分为黑色（已给定数字或空白隔断），部分为白色（待填）。约束包括：
– 每行/列中，同一白色区间内的数字不重复
– 每个白色区间内的数字必须构成连续序列
– 全局：每行/列中 1~n 各出现恰好一次（黑色格子已给定的数字也计入）
2. 候选数排除
为每个空格维护一个候选数集合。通过以下规则逐步排除：
– 行排除：同行已出现的数字不可再用
– 列排除：同列已出现的数字不可再用
– 连续序列约束：根据区间内已填数字，推断该区间的范围，排除超出范围的候选值
3. 唯一解策略
- Naked Single：某空格候选数只剩一个，直接填入
- Hidden Single：某数字在某行/列/区间的候选位置只剩一个，填入该位置
4. 回溯兜底
当候选数排除无法继续推进时，进入回溯搜索。
Java 完整实现
import java.util.*;
/**
* Str8ts 求解器
* 使用候选数排除 + 唯一解策略 + 回溯搜索
*/
public class Str8tsSolver {
private int n;
private int[][] grid; // 0表示空格，-1表示黑色隔断格
private boolean[][][] candidates; // candidates[r][c][v] 表示(r,c)是否可以填v
private List<int[]> emptyCells;
public Str8tsSolver(int n) {
this.n = n;
this.grid = new int[n][n];
this.candidates = new boolean[n][n][n + 1];
this.emptyCells = new ArrayList<>();
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
grid[r][c] = 0;
for (int v = 1; v <= n; v++) {
candidates[r][c][v] = true;
}
}
}
}
/**
* 设置格子：value=-1为黑色隔断，0为空格，1~n为已填数字
*/
public void setCell(int r, int c, int value) {
grid[r][c] = value;
if (value > 0) {
// 固定数字，排除同行同列
for (int i = 0; i < n; i++) {
candidates[r][i][value] = false;
candidates[i][c][value] = false;
}
}
}
/**
* 获取某行中连续的白色区间
*/
private List<List<int[]>> getRowSegments(int row) {
List<List<int[]>> segments = new ArrayList<>();
List<int[]> current = new ArrayList<>();
for (int c = 0; c < n; c++) {
if (grid[row][c] == -1) {
if (!current.isEmpty()) {
segments.add(new ArrayList<>(current));
current.clear();
}
} else {
current.add(new int[]{row, c});
}
}
if (!current.isEmpty()) segments.add(current);
return segments;
}
/**
* 获取某列中连续的白色区间
*/
private List<List<int[]>> getColSegments(int col) {
List<List<int[]>> segments = new ArrayList<>();
List<int[]> current = new ArrayList<>();
for (int r = 0; r < n; r++) {
if (grid[r][col] == -1) {
if (!current.isEmpty()) {
segments.add(new ArrayList<>(current));
current.clear();
}
} else {
current.add(new int[]{r, col});
}
}
if (!current.isEmpty()) segments.add(current);
return segments;
}
/**
* 根据连续序列约束排除候选数
* 例如：某区间长度为3，已填数字为{5}，则该区间的连续序列只能是{4,5,6}或{5,6,7}
* 因此候选数只能是4,5,6或5,6,7中的数字
*/
private boolean applyStraightConstraint() {
boolean changed = false;
for (int r = 0; r < n; r++) {
for (List<int[]> seg : getRowSegments(r)) {
if (applySegmentConstraint(seg)) changed = true;
}
}
for (int c = 0; c < n; c++) {
for (List<int[]> seg : getColSegments(c)) {
if (applySegmentConstraint(seg)) changed = true;
}
}
return changed;
}
private boolean applySegmentConstraint(List<int[]> seg) {
if (seg.size() <= 1) return false;
boolean changed = false;
// 收集已填数字
Set<Integer> filled = new HashSet<>();
for (int[] cell : seg) {
if (grid[cell[0]][cell[1]] > 0) {
filled.add(grid[cell[0]][cell[1]]);
}
}
if (filled.isEmpty()) return false;
int len = seg.size();
// 枚举所有可能的连续序列 [start, start+len-1]
List<Set<Integer>> possibleSets = new ArrayList<>();
for (int start = 1; start + len - 1 <= n; start++) {
Set<Integer> set = new HashSet<>();
boolean valid = true;
for (int i = 0; i < len; i++) {
int v = start + i;
set.add(v);
}
// 已填数字必须全部在该集合中
for (int v : filled) {
if (!set.contains(v)) {
valid = false;
break;
}
}
if (valid) possibleSets.add(set);
}
if (possibleSets.isEmpty()) return false; // 矛盾，由回溯处理
// 合并所有可能的集合，得到允许的候选数
Set<Integer> allowed = new HashSet<>();
for (Set<Integer> s : possibleSets) allowed.addAll(s);
// 排除不在允许集合中的候选数
for (int[] cell : seg) {
int r = cell[0], c = cell[1];
if (grid[r][c] == 0) {
for (int v = 1; v <= n; v++) {
if (candidates[r][c][v] && !allowed.contains(v)) {
candidates[r][c][v] = false;
changed = true;
}
}
}
}
return changed;
}
/**
* 应用Naked Single策略：某格只剩一个候选数则填入
*/
private boolean applyNakedSingles() {
boolean changed = false;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] != 0) continue;
int lastVal = -1, count = 0;
for (int v = 1; v <= n; v++) {
if (candidates[r][c][v]) {
count++;
lastVal = v;
}
}
if (count == 1) {
fillCell(r, c, lastVal);
changed = true;
} else if (count == 0) {
return false; // 矛盾
}
}
}
return changed;
}
private void fillCell(int r, int c, int v) {
grid[r][c] = v;
// 排除同行同列
for (int i = 0; i < n; i++) {
candidates[r][i][v] = false;
candidates[i][c][v] = false;
}
}
/**
* 主求解循环：候选数排除 -> 连续序列 -> Naked Singles，循环直到无法推进
*/
private boolean propagate() {
while (true) {
boolean changed = false;
if (applyNakedSingles()) changed = true;
if (!isValid()) return false;
if (applyStraightConstraint()) changed = true;
if (!isValid()) return false;
if (!changed) break;
}
return true;
}
private boolean isValid() {
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0) {
boolean hasCandidate = false;
for (int v = 1; v <= n; v++) {
if (candidates[r][c][v]) {
hasCandidate = true;
break;
}
}
if (!hasCandidate) return false;
}
}
}
return true;
}
private boolean isComplete() {
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 0) return false;
}
}
return true;
}
/**
* 回溯搜索
*/
private boolean solve() {
if (isComplete()) return true;
// 找到候选数最少的空格
int[] best = null;
int minCount = n + 1;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] != 0) continue;
int count = 0;
for (int v = 1; v <= n; v++) {
if (candidates[r][c][v]) count++;
}
if (count < minCount) {
minCount = count;
best = new int[]{r, c};
if (count <= 1) break;
}
}
if (best != null && minCount <= 1) break;
}
if (best == null || minCount == 0) return false;
int r = best[0], c = best[1];
// 保存当前状态
int[][] gridBackup = new int[n][n];
boolean[][][] candBackup = new boolean[n][n][n + 1];
for (int i = 0; i < n; i++) {
System.arraycopy(grid[i], 0, gridBackup[i], 0, n);
for (int j = 0; j < n; j++) {
System.arraycopy(candidates[i][j], 0, candBackup[i][j], n + 1);
}
}
for (int v = 1; v <= n; v++) {
if (!candidates[r][c][v]) continue;
fillCell(r, c, v);
if (propagate() && solve()) {
return true;
}
// 恢复状态
for (int i = 0; i < n; i++) {
System.arraycopy(gridBackup[i], 0, grid[i], 0, n);
for (int j = 0; j < n; j++) {
System.arraycopy(candBackup[i][j], 0, candidates[i][j], n + 1);
}
}
}
return false;
}
public boolean solvePuzzle() {
if (!propagate()) return false;
return solve();
}
public void printGrid() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == -1) {
System.out.print(" X ");
} else {
System.out.printf("%2d ", grid[i][j]);
}
}
System.out.println();
}
}
public static void main(String[] args) {
// 6x6 Str8ts 示例
Str8tsSolver solver = new Str8tsSolver(6);
// 设置黑色隔断格（-1）和预填数字
// 第0行: [1, -1, 0, 0, -1, 0]
solver.setCell(0, 0, 1);
solver.setCell(0, 1, -1);
solver.setCell(0, 4, -1);
// 第1行: [0, 0, 0, -1, 0, 0]
solver.setCell(1, 3, -1);
// 第2行: [-1, 0, 0, 0, 0, -1]
solver.setCell(2, 0, -1);
solver.setCell(2, 5, -1);
// 第3行: [0, -1, 0, 0, 0, 0]
solver.setCell(3, 1, -1);
// 第4行: [0, 0, -1, 0, 0, 0]
solver.setCell(4, 2, -1);
// 第5行: [0, -1, 0, 0, -1, 6]
solver.setCell(5, 1, -1);
solver.setCell(5, 4, -1);
solver.setCell(5, 5, 6);
System.out.println("初始棋盘（X为黑色隔断）：");
solver.printGrid();
long start = System.currentTimeMillis();
if (solver.solvePuzzle()) {
System.out.println("\n求解结果：");
solver.printGrid();
System.out.println("\n耗时：" + (System.currentTimeMillis() - start) + " ms");
} else {
System.out.println("无解！");
}
}
}
算法复杂度分析
- 候选数排除：每次循环 O(n³)，实际执行轮数受谜题难度限制。
- 回溯搜索：最坏 O(n^(n²))，但约束传播大幅剪枝。
- 空间复杂度：O(n³) 用于候选数数组。
扩展思考
- Hidden Singles：可进一步增强，检查某数字在区间内是否只有一个可填位置。
- 高级策略：Pair/Triple 排除、X-Wing 等数独高级技巧同样适用于 Str8ts。
- 谜题生成：先生成完整解，再添加黑色隔断格并挖空，保证唯一解。
小结
本文用 Java 实现了 Str8ts 求解器，核心采用候选数排除、连续序列约束传播与唯一解策略。代码结构分层清晰，注释详尽，适合作为约束满足问题（CSP）的入门实践。
