Kakuro（数谜）是一种源自日本的逻辑填数字游戏，玩法与填字游戏类似，但填入的是数字而非字母。在一个空白网格中，横向和纵向的连续空白格构成”词”，每个”词”旁边标注了该方向上所有数字之和。填入的数字必须是1-9，且同一个”词”中不能有重复数字。本文用Java实现Kakuro求解器，讲解约束传播、候选数排除与回溯搜索算法的综合运用。
一、Kakuro规则与建模
1.1 游戏规则
- 网格中白色格子需要填入1-9的数字
- 黑色格子将网格分割为横向和纵向的连续序列
- 每个连续序列旁标注了该序列所有数字之和
- 同一序列中数字不能重复
- 所有标注必须同时被满足
1.2 数据结构建模
将Kakuro建模为约束满足问题（CSP）：
- 变量：每个白色格子，定义域为 ({1, 2, …, 9})
- 约束：每个横向/纵向序列构成一个”和约束”——序列中数字之和等于标注值，且数字互不相同
每个约束可表示为：(x_1 + x_2 + … + x_k = S)，其中 (x_i \in {1..9})，且 (x_i \neq x_j)（当 (i \neq j)）。
二、核心算法设计
2.1 和约束的候选数生成
对于长度为 (k)、和为 (S) 的约束，需要找出所有由1-9中 (k) 个不同数字组成、且和为 (S) 的组合。这等价于经典的”整数划分”问题的一个受限版本。使用递归回溯生成所有合法组合，每个组合是一个有序集合。
2.2 约束传播（AC-3）
采用弧相容算法（AC-3）进行约束传播：
- 对每个约束，根据当前各变量的候选值域，筛选出仍可行的组合
- 若某变量在约束的所有可行组合中只能取某个值，则将其值域缩小为该值
- 值域变化后，将所有相邻约束重新加入检查队列
- 重复直到队列为空或发现某变量值域为空（矛盾）
2.3 回溯搜索与MRV启发式
约束传播后若仍未完全求解，则启动回溯搜索：
- MRV启发式（Minimum Remaining Values）：优先选择候选值最少的变量进行赋值，可最大程度减少搜索分支
- 前向检查：赋值后立即检查相邻约束的可行性，提前剪除无效分支
- 约束传播集成：每次赋值后运行一轮AC-3，进一步缩小搜索空间
三、完整Java实现
import java.util.*;
/**
* Kakuro（数谜）求解器
* 运用约束传播、候选数排除与回溯搜索
*/
public class KakuroSolver {
/** 表示一个约束（横向或纵向的连续序列） */
static class Constraint {
int targetSum; // 目标和
List<Cell> cells; // 涉及的格子
List<int[]> validCombinations; // 所有合法数字组合
Constraint(int targetSum) {
this.targetSum = targetSum;
this.cells = new ArrayList<>();
}
/** 生成所有由1-9中不同数字组成、和为targetSum的组合 */
void generateCombinations() {
validCombinations = new ArrayList<>();
int k = cells.size();
generateCombo(new ArrayList<>(), 1, k, 0);
}
private void generateCombo(List<Integer> current, int start,
int remaining, int currentSum) {
if (remaining == 0) {
if (currentSum == targetSum) {
int[] combo = current.stream().mapToInt(Integer::intValue).toArray();
validCombinations.add(combo);
}
return;
}
// 剪枝：剩余数字即使全部取最大/最小也无法达到目标
int minPossible = currentSum;
for (int i = 0; i < remaining; i++) minPossible += (start + i);
int maxPossible = currentSum;
for (int i = 0; i < remaining; i++) maxPossible += (9 - i);
if (minPossible > targetSum || maxPossible < targetSum) return;
for (int num = start; num <= 9; num++) {
current.add(num);
generateCombo(current, num + 1, remaining - 1, currentSum + num);
current.remove(current.size() - 1);
}
}
}
/** 表示一个白色格子 */
static class Cell {
int row, col;
int value; // 已确定的值（0表示未确定）
Set<Integer> domain; // 候选值域
List<Constraint> constraints; // 所属的约束列表
Cell(int row, int col) {
this.row = row; this.col = col;
this.value = 0;
this.domain = new HashSet<>();
for (int i = 1; i <= 9; i++) domain.add(i);
this.constraints = new ArrayList<>();
}
}
private final int rows, cols;
private final Cell[][] grid;
private final List<Constraint> allConstraints;
public KakuroSolver(int rows, int cols) {
this.rows = rows;
this.cols = cols;
this.grid = new Cell[rows][cols];
this.allConstraints = new ArrayList<>();
}
/** 设置白色格子 */
public void setWhite(int r, int c) {
grid[r][c] = new Cell(r, c);
}
/** 添加约束：从(startR, startC)开始，沿指定方向连续len个格子 */
public void addConstraint(int startR, int startC, int len,
int sum, int dR, int dC) {
Constraint cons = new Constraint(sum);
for (int i = 0; i < len; i++) {
int r = startR + i * dR;
int c = startC + i * dC;
cons.cells.add(grid[r][c]);
grid[r][c].constraints.add(cons);
}
cons.generateCombinations();
allConstraints.add(cons);
}
/**
* 约束传播：根据约束筛选每个格子的候选值域
* 返回false表示出现矛盾（无解）
*/
public boolean propagate() {
boolean changed = true;
while (changed) {
changed = false;
for (Constraint cons : allConstraints) {
if (!filterByConstraint(cons)) return false;
}
}
return true;
}
/**
* 根据单个约束筛选值域
*/
private boolean filterByConstraint(Constraint cons) {
// 收集已确定值和未确定格子
Set<Integer> fixedValues = new HashSet<>();
List<Cell> undetermined = new ArrayList<>();
for (Cell cell : cons.cells) {
if (cell.value != 0) fixedValues.add(cell.value);
else undetermined.add(cell);
}
// 遍历所有合法组合，筛选出仍可行的那些
List<int[]> feasible = new ArrayList<>();
for (int[] combo : cons.validCombinations) {
Set<Integer> comboSet = new HashSet<>();
for (int v : combo) comboSet.add(v);
// 已确定值必须是组合的子集
if (!comboSet.containsAll(fixedValues)) continue;
// 组合中不能有与已确定值冲突的数字
boolean conflict = false;
for (int v : combo) {
if (fixedValues.contains(v) && !comboSet.contains(v)) {
// 这个逻辑实际上在上面已经保证了
}
}
// 检查未确定格子的值域是否允许该组合
// 简化：只保留包含所有已确定值的组合
feasible.add(combo);
}
if (feasible.isEmpty()) return false; // 矛盾
// 对未确定格子，收集所有可行组合中该位置可能的值
for (Cell cell : undetermined) {
int idx = cons.cells.indexOf(cell);
Set<Integer> possible = new HashSet<>();
for (int[] combo : feasible) {
possible.add(combo[idx]);
}
// 与当前值域取交集
Set<Integer> oldDomain = new HashSet<>(cell.domain);
cell.domain.retainAll(possible);
if (cell.domain.isEmpty()) return false; // 矛盾
if (!cell.domain.equals(oldDomain)) changed = true;
}
return true;
}
/**
* MRV启发式：选择候选值最少的未确定格子
*/
private Cell selectMRV() {
Cell best = null;
int minSize = 10;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
Cell cell = grid[r][c];
if (cell != null && cell.value == 0) {
if (cell.domain.size() < minSize) {
minSize = cell.domain.size();
best = cell;
}
}
}
}
return best;
}
/**
* 回溯搜索主函数
*/
public boolean solve() {
// 初始约束传播
if (!propagate()) return false;
return backtrack();
}
private boolean backtrack() {
Cell cell = selectMRV();
if (cell == null) return true; // 全部确定
// 保存状态用于回溯
List<Set<Integer>> savedDomains = new ArrayList<>();
for (Constraint cons : cell.constraints) {
for (Cell c : cons.cells) {
savedDomains.add(new HashSet<>(c.domain));
}
}
for (int val : new ArrayList<>(cell.domain)) {
cell.value = val;
cell.domain.clear();
cell.domain.add(val);
if (propagate()) {
if (backtrack()) return true;
}
// 回溯：恢复所有值域
cell.value = 0;
int idx = 0;
for (Constraint cons : cell.constraints) {
for (Cell c : cons.cells) {
c.domain = savedDomains.get(idx++);
}
}
}
return false;
}
/** 打印当前网格状态 */
public void printGrid() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == null) System.out.print(" # ");
else if (grid[r][c].value == 0) System.out.print(" . ");
else System.out.printf(" %2d ", grid[r][c].value);
}
System.out.println();
}
}
// ==================== 主程序 ====================
public static void main(String[] args) {
System.out.println("===== Kakuro（数谜）求解器 =====\n");
// 构建一个5x5的示例谜题
// 布局：
// # # 3\ 4\ #
// # 4\ . . 4\
// 3\ . . . .
// 4\ . . # #
// # 4\ . # #
//
// 标注格式：横向和\纵向和
System.out.println("【示例】5x5 Kakuro谜题");
KakuroSolver solver = new KakuroSolver(5, 5);
// 设置白色格子
int[][] whites = {
{0,2},{0,3},
{1,1},{1,2},{1,3},{1,4},
{2,0},{2,1},{2,2},{2,3},{2,4},
{3,0},{3,1},{3,2},
{4,1},{4,2}
};
for (int[] w : whites) solver.setWhite(w[0], w[1]);
// 添加横向约束 (row, col, len, sum, dR, dC)
solver.addConstraint(0, 2, 2, 3, 0, 1); // row0: 3\ = . . (长度2和3)
solver.addConstraint(1, 1, 3, 4, 0, 1); // row1: 4\ = . . . (长度3和4)
solver.addConstraint(2, 0, 5, 3, 0, 1); // row2: 3\ = . . . . . (长度5和3)
solver.addConstraint(3, 0, 3, 4, 0, 1); // row3: 4\ = . . . (长度3和4)
solver.addConstraint(4, 1, 2, 4, 0, 1); // row4: 4\ = . . (长度2和4)
// 添加纵向约束
solver.addConstraint(0, 2, 3, 4, 1, 0); // col2: \4 = . . . (长度3和4)
solver.addConstraint(0, 3, 2, 3, 1, 0); // col3: \3 = . . (长度2和3)
solver.addConstraint(1, 4, 3, 4, 1, 0); // col4: \4 = . . . (长度3和4)
solver.addConstraint(2, 0, 2, 3, 1, 0); // col0: \3 = . . (长度2和3)
solver.addConstraint(2, 1, 2, 4, 1, 0); // col1: \4 = . . (长度2和4)
System.out.println("初始状态（.表示空白）：");
solver.printGrid();
long start = System.currentTimeMillis();
boolean solved = solver.solve();
long elapsed = System.currentTimeMillis() - start;
System.out.println("\n求解结果：" + (solved ? "成功" : "失败")
+ "，耗时 " + elapsed + "ms");
if (solved) solver.printGrid();
// 验证
if (solved) {
System.out.println("\n验证：");
for (Constraint cons : solver.allConstraints) {
int sum = 0;
for (Cell c : cons.cells) sum += c.value;
System.out.println(" 约束和=" + cons.targetSum
+ ", 实际和=" + sum
+ ", " + (sum == cons.targetSum ? "✓" : "✗"));
}
}
}
}
四、复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 组合生成 | (O(C(k, S))) | (O(C(k, S) \cdot k)) | 受和与长度限制，通常很小 |
| 约束传播 | (O(n \cdot m \cdot c)) | (O(n \cdot m)) | (n)约束数，(m)格子数，(c)组合数 |
| MRV选择 | (O(m)) | (O(1)) | 遍历所有未确定格子 |
| 回溯搜索 | 最坏 (O(9^m)) | (O(m \cdot d)) | (d)为约束相关的格子数 |
Kakuro虽然属于NP完全问题，但约束传播能极大缩小搜索空间。对于标准谜题规模（<100格子），实际求解时间通常在毫秒级。
五、扩展思考
- ** Dancing Links（DLX）**：将Kakuro精确覆盖问题建模为DLX矩阵，利用Algorithm X高效求解，特别适合大规模谜题。
- 杀手数独变体：Kakuro与数独的结合——在9×9网格中既满足数独规则又满足Kakuro的和约束，求解难度大幅提升。
- 谜题生成器：逆向运用求解器，从一个完整解出发，逐步移除提示数字，确保生成的谜题有唯一解且难度可控。
Kakuro求解器是约束满足问题的经典教学案例，约束传播与回溯搜索的配合体现了”先推理、后猜测”的问题求解哲学。
