每日算法 — 使用java实现杀手数独：约束传播与候选数排除

引言

杀手数独（Killer Sudoku）是标准数独的变体，增加了虚线框（Cage）约束：每个Cage内数字之和必须等于给定的目标值，且Cage内数字不能重复。这一额外约束使求解难度显著提升——单纯回溯搜索会陷入组合爆炸。本文将用Java实现杀手数独求解器，重点讲解约束传播、候选数排除与区域和校验的高效算法。

核心算法原理

1. 约束类型

杀手数独包含四层约束：

2. 约束传播策略

利用和的唯一分解提前剪枝：

• $n$ 个不同数字之和为 $S$ 的组合数有限，可预计算所有可能组合
• 例如：3个不同数字和为7，仅有一种组合 ${1,2,4}$
• 利用此信息直接确定某些格子的候选数

3. 候选数动态维护

每个格子维护候选数集合 $C(cell)$。当某格确定值 $v$ 时：
– 同行/同列/同宫格子的候选数删除 $v$
– 同Cage格子的候选数删除 $v$，并更新Cage剩余和

Java完整实现

package killersudoku;

import java.util.*;

/**
 * 杀手数独求解器
 * 核心算法：约束传播 + 候选数排除 + 回溯搜索
 */
public class KillerSudokuSolver {
    private static final int SIZE = 9;
    private int[][] board; // 0表示未填

    // 约束状态
    private boolean[][] rowUsed = new boolean[SIZE][10];
    private boolean[][] colUsed = new boolean[SIZE][10];
    private boolean[][] boxUsed = new boolean[SIZE][10];

    // Cage定义
    static class Cage {
        List<int[]> cells = new ArrayList<>(); // 每个cell是{row,col}
        int targetSum;
        int remainingSum;
        Set<Integer> usedValues = new HashSet<>();

        Cage(int sum) {
            this.targetSum = sum;
            this.remainingSum = sum;
        }

        void addCell(int r, int c) { cells.add(new int[]{r,c}); }
    }

    private List<Cage> cages = new ArrayList<>();
    private int[][] cageId; // 每个格子所属的Cage索引

    // 每个格子的候选数
    private Set<Integer>[][] candidates;

    // 预计算：n个不同数字(1-9)之和为S的所有组合
    private static Map<String, List<Set<Integer>>> sumCombinations = new HashMap<>();

    static {
        precomputeCombinations();
    }

    static void precomputeCombinations() {
        // 枚举1-9的所有子集
        for (int mask = 1; mask < (1 << 9); mask++) {
            Set<Integer> set = new HashSet<>();
            int sum = 0;
            for (int i = 0; i < 9; i++) {
                if ((mask & (1 << i)) != 0) {
                    set.add(i + 1);
                    sum += i + 1;
                }
            }
            String key = set.size() + ":" + sum;
            sumCombinations.computeIfAbsent(key, k -> new ArrayList<>()).add(set);
        }
    }

    public KillerSudokuSolver() {
        board = new int[SIZE][SIZE];
        cageId = new int[SIZE][SIZE];
        for (int[] row : cageId) Arrays.fill(row, -1);

        candidates = new HashSet[SIZE][SIZE];
        for (int r = 0; r < SIZE; r++) {
            for (int c = 0; c < SIZE; c++) {
                candidates[r][c] = new HashSet<>();
                for (int v = 1; v <= 9; v++) candidates[r][c].add(v);
            }
        }
    }

    /**
     * 添加Cage约束
     */
    public void addCage(int sum, int[][] cells) {
        Cage cage = new Cage(sum);
        for (int[] cell : cells) {
            cage.addCell(cell[0], cell[1]);
            cageId[cell[0]][cell[1]] = cages.size();
        }
        cages.add(cage);
    }

    /**
     * 初始约束传播：利用Cage和约束缩减候选数
     */
    public boolean initialPropagation() {
        boolean changed = true;
        while (changed) {
            changed = false;

            // 1. 利用Cage的唯一分解
            for (Cage cage : cages) {
                if (cage.cells.size() == cage.usedValues.size()) continue;

                int remainingCells = cage.cells.size() - cage.usedValues.size();
                String key = remainingCells + ":" + cage.remainingSum;
                List<Set<Integer>> combos = sumCombinations.getOrDefault(key, Collections.emptyList());

                if (combos.size() == 1) {
                    // 唯一组合！所有未填格子的候选数只能是该组合中的数
                    Set<Integer> validSet = new HashSet<>(combos.get(0));
                    validSet.removeAll(cage.usedValues);

                    for (int[] cell : cage.cells) {
                        int r = cell[0], c = cell[1];
                        if (board[r][c] == 0) {
                            Set<Integer> newCand = new HashSet<>(candidates[r][c]);
                            newCand.retainAll(validSet);
                            if (newCand.size() < candidates[r][c].size()) {
                                candidates[r][c] = newCand;
                                changed = true;
                            }
                        }
                    }
                }
            }

            // 2. 标准数独约束：隐藏单数、显性单数
            for (int r = 0; r < SIZE; r++) {
                for (int c = 0; c < SIZE; c++) {
                    if (board[r][c] != 0) continue;

                    Set<Integer> impossible = new HashSet<>();
                    for (int v = 1; v <= 9; v++) {
                        if (rowUsed[r][v] || colUsed[c][v] || boxUsed[getBox(r,c)][v]) {
                            impossible.add(v);
                        }
                    }

                    Set<Integer> newCand = new HashSet<>(candidates[r][c]);
                    newCand.removeAll(impossible);
                    if (newCand.size() < candidates[r][c].size()) {
                        candidates[r][c] = newCand;
                        changed = true;
                    }

                    // 候选数为空 -> 矛盾
                    if (candidates[r][c].isEmpty()) return false;
                }
            }

            // 3. 若某格候选数唯一，直接填入
            for (int r = 0; r < SIZE; r++) {
                for (int c = 0; c < SIZE; c++) {
                    if (board[r][c] == 0 && candidates[r][c].size() == 1) {
                        int val = candidates[r][c].iterator().next();
                        if (!place(r, c, val)) return false;
                        changed = true;
                    }
                }
            }
        }
        return true;
    }

    /**
     * 在指定位置填入数字，更新所有约束
     */
    private boolean place(int r, int c, int val) {
        board[r][c] = val;
        rowUsed[r][val] = true;
        colUsed[c][val] = true;
        boxUsed[getBox(r,c)][val] = true;
        candidates[r][c].clear();
        candidates[r][c].add(val);

        // 更新Cage状态
        int cid = cageId[r][c];
        if (cid >= 0) {
            Cage cage = cages.get(cid);
            if (cage.usedValues.contains(val)) return false; // Cage内重复
            cage.usedValues.add(val);
            cage.remainingSum -= val;
            if (cage.remainingSum < 0) return false; // 和超出
        }

        return true;
    }

    private void unplace(int r, int c, int val) {
        board[r][c] = 0;
        rowUsed[r][val] = false;
        colUsed[c][val] = false;
        boxUsed[getBox(r,c)][val] = false;

        int cid = cageId[r][c];
        if (cid >= 0) {
            Cage cage = cages.get(cid);
            cage.usedValues.remove(val);
            cage.remainingSum += val;
        }

        // 恢复候选数需要重新计算，简化处理：回溯时重新初始化
    }

    private int getBox(int r, int c) { return (r / 3) * 3 + (c / 3); }

    /**
     * 回溯搜索主函数
     */
    public boolean solve() {
        if (!initialPropagation()) return false;
        return backtrack();
    }

    /**
     * 带启发式的回溯搜索
     * 选择候选数最少（MRV）的格子优先尝试
     */
    private boolean backtrack() {
        // 找MRV格子
        int[] next = findMRV();
        if (next == null) return true; // 全部填完

        int r = next[0], c = next[1];
        List<Integer> orderedCandidates = orderCandidates(r, c);

        for (int val : orderedCandidates) {
            if (isValid(r, c, val)) {
                // 保存状态
                Set<Integer>[][] savedCandidates = deepCopyCandidates();

                if (place(r, c, val)) {
                    if (backtrack()) return true;
                }

                // 恢复状态
                unplace(r, c, val);
                restoreCandidates(savedCandidates);
            }
        }

        return false;
    }

    private int[] findMRV() {
        int minSize = 10;
        int[] best = null;
        for (int r = 0; r < SIZE; r++) {
            for (int c = 0; c < SIZE; c++) {
                if (board[r][c] == 0 && candidates[r][c].size() < minSize) {
                    minSize = candidates[r][c].size();
                    best = new int[]{r, c};
                }
            }
        }
        return best;
    }

    private List<Integer> orderCandidates(int r, int c) {
        List<Integer> list = new ArrayList<>(candidates[r][c]);
        // 按约束强度排序：优先尝试对邻居影响大的值
        list.sort((a, b) -> {
            int ca = constraintImpact(r, c, a);
            int cb = constraintImpact(r, c, b);
            return Integer.compare(cb, ca); // 影响大的优先
        });
        return list;
    }

    private int constraintImpact(int r, int c, int val) {
        int count = 0;
        // 统计同行/列/宫中有多少格子的候选数包含val
        for (int i = 0; i < SIZE; i++) {
            if (board[r][i] == 0 && candidates[r][i].contains(val)) count++;
            if (board[i][c] == 0 && candidates[i][c].contains(val)) count++;
        }
        int br = (r / 3) * 3, bc = (c / 3) * 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[br+i][bc+j] == 0 && candidates[br+i][bc+j].contains(val)) count++;
            }
        }
        return count;
    }

    private boolean isValid(int r, int c, int val) {
        if (rowUsed[r][val] || colUsed[c][val] || boxUsed[getBox(r,c)][val]) return false;
        int cid = cageId[r][c];
        if (cid >= 0) {
            Cage cage = cages.get(cid);
            if (cage.usedValues.contains(val)) return false;
            if (cage.remainingSum - val < 0) return false;
        }
        return true;
    }

    @SuppressWarnings("unchecked")
    private Set<Integer>[][] deepCopyCandidates() {
        Set<Integer>[][] copy = new HashSet[SIZE][SIZE];
        for (int r = 0; r < SIZE; r++) {
            for (int c = 0; c < SIZE; c++) {
                copy[r][c] = new HashSet<>(candidates[r][c]);
            }
        }
        return copy;
    }

    private void restoreCandidates(Set<Integer>[][] saved) {
        for (int r = 0; r < SIZE; r++) {
            for (int c = 0; c < SIZE; c++) {
                candidates[r][c] = saved[r][c];
            }
        }
    }

    public void printBoard() {
        for (int r = 0; r < SIZE; r++) {
            for (int c = 0; c < SIZE; c++) {
                System.out.print(board[r][c] == 0 ? ". " : board[r][c] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        KillerSudokuSolver solver = new KillerSudokuSolver();

        // 示例：设置一个简单的Cage布局
        // 第一行Cage：和为10，包含(0,0)(0,1) -> 只能是1+9,2+8,3+7,4+6
        solver.addCage(10, new int[][]{{0,0},{0,1}});
        solver.addCage(17, new int[][]{{0,2},{0,3},{0,4}});
        solver.addCage(8, new int[][]{{0,5},{0,6}});
        solver.addCage(15, new int[][]{{0,7},{0,8}});

        // 添加更多Cage以形成可解谜题...
        // 实际使用时需完整的Cage定义

        System.out.println("求解中...");
        if (solver.solve()) {
            System.out.println("求解成功！");
            solver.printBoard();
        } else {
            System.out.println("无解或Cage定义不完整");
        }
    }
}

复杂度分析

扩展思考

1. Cage生成算法：随机生成有唯一解的杀手数独，需从完整解出发随机合并相邻格子为Cage
2. 难度评估：可通过”求解所需回溯步数”或”初始约束传播确定格子的比例”量化难度
3. 高级技巧：引入”裸对/隐对”、”X-Wing”等 fish 模式可进一步提升求解效率

总结

杀手数独是约束满足问题（CSP）的经典实例。通过预计算和的唯一分解、动态维护候选数集合以及MRV启发式，我们将看似指数级的问题控制在多项式时间内。这些技术同样适用于调度、配置等其他CSP场景。