Kakuro（数谜/交叉求和）是一种结合了填字游戏和数独元素的逻辑拼图。玩家需要在一个网格中填入数字 1-9，使得每行和每列的连续空白格中的数字之和等于该组格旁给出的线索值，且同一组中不允许出现重复数字。本文用 Java 实现 Kakuro 的自动求解器，核心算法采用约束传播（Constraint Propagation）与带前向检查（Forward Checking）的回溯搜索。
核心算法思路
Kakuro 求解可建模为约束满足问题（CSP），其中：
– 变量：每个空白格，定义域为 {1, 2, …, 9}。
– 约束：每组连续空白格（称为一个”run”）内的数字之和等于线索值，且组内无重复。
求解策略：
- 预处理与约束强化：
- 识别所有行 run 和列 run。
- 对每个 run，计算其数字组合的所有可能排列。例如和为 7、长度为 2 的 run，只有 {1,6}、{2,5}、{3,4} 三种组合。
-
利用这些预计算的组合来大幅缩减每个格子的定义域。
-
约束传播（弧相容性 AC-3）：
- 每个空白格同时属于一个行 run 和一个列 run。
- 当一个格子的候选值减少时，重新计算其所属 run 的合法组合，进一步缩减同组其他格子的候选值。
-
迭代此过程直至达到不动点。
-
回溯搜索与 MRV 启发式：
- 当约束传播无法继续时，选择候选值最少的格子（Minimum Remaining Values, MRV）进行赋值。
- 每次赋值后执行前向检查：如果某格子的定义域变为空，立即回退。
Java 实现
import java.util.*;
public class KakuroSolver {
private int rows, cols;
// 0=黑格(无值), 1=空白格, 2=线索格(下行保存线索值)
private int[][] cellType;
// 行线索: rowClues[r][c] 表示该黑格下方 run 的和
private int[][] rowClues;
// 列线索: colClues[r][c] 表示该黑格右方 run 的和
private int[][] colClues;
// 每个空白格的当前候选值集合
private Set<Integer>[][] domains;
// 每个空白格的值（0=未填）
private int[][] values;
// 所有行 run 和列 run
private List<Run> rowRuns = new ArrayList<>();
private List<Run> colRuns = new ArrayList<>();
public KakuroSolver(int[][] cellType, int[][] rowClues, int[][] colClues) {
this.rows = cellType.length;
this.cols = cellType[0].length;
this.cellType = cellType;
this.rowClues = rowClues;
this.colClues = colClues;
this.values = new int[rows][cols];
this.domains = new Set[rows][cols];
initRuns();
initDomains();
}
/**
* 识别所有行 run 和列 run
*/
private void initRuns() {
// 行 run
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (cellType[r][c] == 2 && rowClues[r][c] > 0) {
List<int[]> cells = new ArrayList<>();
int cc = c + 1;
while (cc < cols && cellType[r][cc] == 1) {
cells.add(new int[]{r, cc});
cc++;
}
if (cells.size() > 0) {
rowRuns.add(new Run(rowClues[r][c], cells));
}
}
}
}
// 列 run
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (cellType[r][c] == 2 && colClues[r][c] > 0) {
List<int[]> cells = new ArrayList<>();
int rr = r + 1;
while (rr < rows && cellType[rr][c] == 1) {
cells.add(new int[]{rr, c});
rr++;
}
if (cells.size() > 0) {
colRuns.add(new Run(colClues[r][c], cells));
}
}
}
}
}
/**
* 初始化每个空白格的定义域为 {1,...,9}
*/
private void initDomains() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (cellType[r][c] == 1) {
Set<Integer> domain = new HashSet<>();
for (int i = 1; i <= 9; i++) domain.add(i);
domains[r][c] = domain;
}
}
}
// 用 run 的约束进一步缩减定义域
boolean changed;
do {
changed = false;
for (Run run : rowRuns) {
if (narrowDomain(run)) changed = true;
}
for (Run run : colRuns) {
if (narrowDomain(run)) changed = true;
}
} while (changed);
}
/**
* 根据 run 的约束缩减其包含格子的定义域
*/
private boolean narrowDomain(Run run) {
boolean changed = false;
List<Set<Integer>> cellDomains = new ArrayList<>();
for (int[] cell : run.cells) {
Set<Integer> d = new HashSet<>();
if (values[cell[0]][cell[1]] > 0) {
d.add(values[cell[0]][cell[1]]);
} else {
d.addAll(domains[cell[0]][cell[1]]);
}
cellDomains.add(d);
}
// 枚举该 run 的所有合法组合
List<int[]> validCombos = new ArrayList<>();
enumerateCombinations(run, cellDomains, 0, new int[run.cells.size()], validCombos);
if (validCombos.isEmpty()) {
throw new IllegalStateException("No valid combination for run with sum=" + run.sum);
}
// 对每个格子，求所有合法组合中该位置可能值的并集
for (int i = 0; i < run.cells.size(); i++) {
int[] cell = run.cells.get(i);
if (values[cell[0]][cell[1]] > 0) continue;
Set<Integer> possible = new HashSet<>();
for (int[] combo : validCombos) {
possible.add(combo[i]);
}
Set<Integer> original = domains[cell[0]][cell[1]];
if (!original.equals(possible)) {
Set<Integer> intersection = new HashSet<>(original);
intersection.retainAll(possible);
if (intersection.isEmpty()) {
throw new IllegalStateException("Domain emptied for cell [" + cell[0] + "," + cell[1] + "]");
}
domains[cell[0]][cell[1]] = intersection;
changed = true;
}
}
return changed;
}
/**
* 递归枚举某 run 的所有合法数字组合
*/
private void enumerateCombinations(Run run, List<Set<Integer>> cellDomains,
int pos, int[] current, List<int[]> results) {
if (pos == run.cells.size()) {
// 检查是否有重复
Set<Integer> used = new HashSet<>();
for (int v : current) {
if (!used.add(v)) return;
}
// 检查是否等于目标和
int sum = 0;
for (int v : current) sum += v;
if (sum == run.sum) {
results.add(current.clone());
}
return;
}
for (int val : cellDomains.get(pos)) {
current[pos] = val;
// 剪枝：若当前和已超过目标和，跳过
int partialSum = 0;
for (int i = 0; i <= pos; i++) partialSum += current[i];
int minRemaining = 0, maxRemaining = 0;
for (int i = pos + 1; i < run.cells.size(); i++) {
minRemaining += Collections.min(cellDomains.get(i));
maxRemaining += Collections.max(cellDomains.get(i));
}
if (partialSum + minRemaining > run.sum || partialSum + maxRemaining < run.sum) {
continue;
}
// 检查重复
boolean dup = false;
for (int i = 0; i < pos; i++) {
if (current[i] == val) { dup = true; break; }
}
if (dup) continue;
enumerateCombinations(run, cellDomains, pos + 1, current, results);
}
}
/**
* 主求解入口：带 MRV 的回溯搜索
*/
public boolean solve() {
// 检查是否已解完
int[] next = findMRVCell();
if (next == null) return true; // 所有格子已填
int r = next[0], c = next[1];
Set<Integer> domain = new HashSet<>(domains[r][c]);
for (int val : domain) {
// 保存状态
Set<Integer> savedDomain = new HashSet<>(domains[r][c]);
values[r][c] = val;
domains[r][c] = new HashSet<>(Collections.singletonList(val));
// 前向检查：更新相关 run 中格子的定义域
Map<int[], Set<Integer>> affected = new HashMap<>();
boolean consistent = true;
try {
boolean changed;
do {
changed = false;
for (Run run : rowRuns) {
if (containsCell(run, r, c)) {
if (narrowDomain(run)) changed = true;
}
}
for (Run run : colRuns) {
if (containsCell(run, r, c)) {
if (narrowDomain(run)) changed = true;
}
}
} while (changed);
} catch (IllegalStateException e) {
consistent = false;
}
if (consistent && solve()) {
return true;
}
// 回退
values[r][c] = 0;
domains[r][c] = savedDomain;
// 需要恢复所有受影响格子的定义域（简化处理：重新初始化）
restoreDomains();
}
return false;
}
private boolean containsCell(Run run, int r, int c) {
for (int[] cell : run.cells) {
if (cell[0] == r && cell[1] == c) return true;
}
return false;
}
/**
* 寻找候选值最少的未填格子（MRV 启发式）
*/
private int[] findMRVCell() {
int[] best = null;
int minSize = 10;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (cellType[r][c] == 1 && values[r][c] == 0) {
int size = domains[r][c].size();
if (size < minSize) {
minSize = size;
best = new int[]{r, c};
}
}
}
}
return best;
}
private void restoreDomains() {
// 简化恢复：基于当前已填值重新计算所有定义域
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (cellType[r][c] == 1 && values[r][c] == 0) {
domains[r][c] = new HashSet<>();
for (int i = 1; i <= 9; i++) domains[r][c].add(i);
}
}
}
boolean changed;
do {
changed = false;
for (Run run : rowRuns) {
if (narrowDomain(run)) changed = true;
}
for (Run run : colRuns) {
if (narrowDomain(run)) changed = true;
}
} while (changed);
}
public void printSolution() {
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (cellType[r][c] == 0) System.out.print("■■■");
else if (cellType[r][c] == 2) System.out.print("\\" + String.format("%02d", rowClues[r][c] > 0 ? rowClues[r][c] : 0));
else System.out.print(" " + values[r][c] + " ");
}
System.out.println();
}
}
static class Run {
int sum;
List<int[]> cells;
Run(int sum, List<int[]> cells) { this.sum = sum; this.cells = cells; }
}
public static void main(String[] args) {
// 示例：一个 5x5 的 Kakuro 谜题
// cellType: 0=黑格, 1=空白, 2=线索格
int[][] cellType = {
{0, 2, 2, 0, 0},
{2, 1, 1, 2, 0},
{2, 1, 1, 1, 2},
{0, 2, 1, 1, 1},
{0, 0, 2, 1, 1}
};
int[][] rowClues = {
{0, 4, 6, 0, 0},
{3, 0, 0, 4, 0},
{7, 0, 0, 0, 6},
{0, 3, 0, 0, 0},
{0, 0, 4, 0, 0}
};
int[][] colClues = {
{0, 3, 4, 0, 0},
{4, 0, 0, 10, 0},
{6, 0, 0, 0, 4},
{0, 4, 0, 0, 0},
{0, 0, 6, 0, 0}
};
KakuroSolver solver = new KakuroSolver(cellType, rowClues, colClues);
if (solver.solve()) {
System.out.println("Solved!");
solver.printSolution();
} else {
System.out.println("No solution found.");
}
}
}
复杂度分析
时间复杂度：预处理阶段枚举每个 run 的合法组合，最坏情况下为 C(9, k) × k!（k 为 run 长度），但由于和约束的存在，实际组合数远小于此。回溯搜索最坏为 O(9^n)，其中 n 为空白格数，但 MRV 启发式和约束传播通常能将搜索空间压缩数个数量级。
空间复杂度：存储网格、定义域和 run 列表，O(R×C×9 + 总 run 数)。
算法优化
- 组合预计算：对于所有可能的（和，长度）组合，预先计算合法数字集合并缓存，避免运行时重复枚举。
- 隐藏单格（Hidden Single）：如果某 run 中某个数字只能放在某个特定格子中，则直接确定该格子的值。
- ** Dancing Links**：对于极大规模的 Kakuro，可使用 DLX（Algorithm X）精确覆盖算法求解。
总结
Kakuro 求解器展示了约束满足问题求解的经典范式——约束传播负责消除不可能性，回溯搜索负责处理不确定性的分支选择。通过将行/列的双重约束建模为 run 的组合问题，并利用 MRV 启发式优先处理最受限的变量，求解器能够高效地处理中等难度的 Kakuro 谜题。该框架同样适用于数独、拉丁方等类似的逻辑拼图求解。
