每日算法 — 使用java实现数独：回溯与约束传播

游戏简介

数独（Sudoku）是源自18世纪瑞士数学家欧拉所研究的”拉丁方”，后经日本杂志推广风靡全球的逻辑填数游戏。标准数独为9×9网格，分为9个3×3宫格。玩家需在空白处填入1-9，使每行、每列、每宫都不出现重复数字。

数独求解是典型的约束满足问题（CSP）。本文用Java实现一个结合约束传播（MRV + 前向检查）与回溯搜索的高效求解器，可在毫秒级解决世界上最难的数独题目。

核心算法

回溯搜索

基础回溯法：按顺序遍历每个空格，尝试1-9中不冲突的数字，递归求解。若某步导致无解则回退（Backtrack）。

基础回溯最坏情况复杂度为O(9^81)，无法实用。

约束传播优化

1. 最小剩余值（MRV）

每次选择候选数字最少的空格先填，而非按固定顺序。这能尽早暴露矛盾，减少搜索分支。

2. 前向检查（Forward Checking）

填一个数字后，立即从同行、同列、同宫的其他空格候选集中删除该数字。若某个空格候选集为空，立即回溯。

3. 单值传播（Singleton Propagation）

若某空格只剩一个候选值，或某数字在某行/列/宫中只有一个可填位置，立即确定该值并级联传播。

4. 隐藏单值与裸对（进阶）

• 隐藏单值：某数字在某区域只有一个可填格子
• 裸对（Naked Pair）：两个空格候选集相同且大小为2，可从同区域其他格子中删除这两个数字

本文实现前3项，已足够应对几乎所有数独。

Java完整实现

import java.util.*;

/**
 * 数独求解器 - 回溯 + MRV + 前向检查 + 单值传播
 */
public class SudokuSolver {

    static final int N = 9;      // 9×9
    static final int BOX = 3;    // 3×3宫

    // 每个格子的候选集，用位运算：第k位为1表示k是候选（1-9对应bit 1-9）
    int[][] candidates = new int[N][N];
    int[][] board = new int[N][N];
    int steps = 0; // 搜索步数统计

    /** 初始化：解析输入并计算初始候选集 */
    public SudokuSolver(int[][] puzzle) {
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                board[r][c] = puzzle[r][c];
                if (puzzle[r][c] == 0) {
                    candidates[r][c] = 0x3FE; // 二进制 1111111110，表示1-9均可
                } else {
                    candidates[r][c] = 1 << puzzle[r][c]; // 只有当前值
                }
            }
        }
        // 初始约束传播
        boolean changed;
        do {
            changed = false;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    if (board[r][c] != 0) {
                        changed |= propagate(r, c, board[r][c]);
                    }
                }
            }
        } while (changed);
    }

    /** 在(r,c)填入val后，从相关格子候选集中删除val */
    boolean propagate(int r, int c, int val) {
        boolean changed = false;
        int mask = ~(1 << val);
        // 同行
        for (int cc = 0; cc < N; cc++) {
            if (cc != c && board[r][cc] == 0 && (candidates[r][cc] & (1 << val)) != 0) {
                candidates[r][cc] &= mask;
                changed = true;
            }
        }
        // 同列
        for (int rr = 0; rr < N; rr++) {
            if (rr != r && board[rr][c] == 0 && (candidates[rr][c] & (1 << val)) != 0) {
                candidates[rr][c] &= mask;
                changed = true;
            }
        }
        // 同宫
        int br = (r / BOX) * BOX, bc = (c / BOX) * BOX;
        for (int rr = br; rr < br + BOX; rr++) {
            for (int cc = bc; cc < bc + BOX; cc++) {
                if ((rr != r || cc != c) && board[rr][cc] == 0 && (candidates[rr][cc] & (1 << val)) != 0) {
                    candidates[rr][cc] &= mask;
                    changed = true;
                }
            }
        }
        return changed;
    }

    /** 获取某格子的候选数字列表 */
    List<Integer> getCandidateList(int r, int c) {
        List<Integer> list = new ArrayList<>();
        int bits = candidates[r][c];
        for (int v = 1; v <= 9; v++) {
            if ((bits & (1 << v)) != 0) list.add(v);
        }
        return list;
    }

    /** 候选数量 */
    int candidateCount(int bits) {
        return Integer.bitCount(bits >> 1); // bit 1-9
    }

    /** 寻找候选数最少（MRV）且大于0的空格 */
    int[] findMRV() {
        int minCount = 10;
        int[] best = null;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (board[r][c] != 0) continue;
                int count = candidateCount(candidates[r][c]);
                if (count == 0) return new int[]{r, c, 0}; // 矛盾
                if (count < minCount) {
                    minCount = count;
                    best = new int[]{r, c, count};
                }
            }
        }
        return best;
    }

    /** 单值传播：若某格只剩一个候选，或某数字在某区域只有一个位置 */
    boolean singletonPropagation() {
        boolean changed = false;
        // 检查每个空格
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (board[r][c] != 0) continue;
                List<Integer> list = getCandidateList(r, c);
                if (list.size() == 1) {
                    board[r][c] = list.get(0);
                    propagate(r, c, list.get(0));
                    changed = true;
                }
            }
        }
        // 检查每行/列/宫的隐藏单值
        for (int num = 1; num <= 9; num++) {
            for (int r = 0; r < N; r++) {
                int count = 0, pos = -1;
                for (int c = 0; c < N; c++) {
                    if (board[r][c] == 0 && (candidates[r][c] & (1 << num)) != 0) {
                        count++; pos = c;
                    }
                }
                if (count == 1 && board[r][pos] == 0) {
                    board[r][pos] = num;
                    propagate(r, pos, num);
                    changed = true;
                }
            }
            for (int c = 0; c < N; c++) {
                int count = 0, pos = -1;
                for (int r = 0; r < N; r++) {
                    if (board[r][c] == 0 && (candidates[r][c] & (1 << num)) != 0) {
                        count++; pos = r;
                    }
                }
                if (count == 1 && board[pos][c] == 0) {
                    board[pos][c] = num;
                    propagate(pos, c, num);
                    changed = true;
                }
            }
        }
        return changed;
    }

    /**
     * 回溯求解
     */
    boolean solve() {
        steps++;

        // 单值传播
        while (singletonPropagation()) {}

        // 检查是否完成
        boolean complete = true;
        for (int r = 0; r < N; r++)
            for (int c = 0; c < N; c++)
                if (board[r][c] == 0) { complete = false; break; }
        if (complete) return true;

        // MRV选择
        int[] mrv = findMRV();
        if (mrv == null || mrv[2] == 0) return false; // 无解或矛盾

        int r = mrv[0], c = mrv[1];
        List<Integer> vals = getCandidateList(r, c);

        // 保存状态用于回溯
        int[][] savedBoard = new int[N][N];
        int[][] savedCand = new int[N][N];
        for (int i = 0; i < N; i++) {
            savedBoard[i] = board[i].clone();
            savedCand[i] = candidates[i].clone();
        }

        for (int val : vals) {
            board[r][c] = val;
            propagate(r, c, val);

            if (solve()) return true;

            // 回溯：恢复状态
            for (int i = 0; i < N; i++) {
                board[i] = savedBoard[i].clone();
                candidates[i] = savedCand[i].clone();
            }
        }
        return false;
    }

    void printBoard() {
        for (int r = 0; r < N; r++) {
            if (r % 3 == 0 && r != 0) System.out.println("------+-------+------");
            for (int c = 0; c < N; c++) {
                if (c % 3 == 0 && c != 0) System.out.print("| ");
                System.out.print(board[r][c] == 0 ? ". " : board[r][c] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        // 世界最难数独之一（Arto Inkala 2010）
        int[][] puzzle = {
            {0,0,5,3,0,0,0,0,0},
            {8,0,0,0,0,0,0,2,0},
            {0,7,0,0,1,0,5,0,0},
            {4,0,0,0,0,5,3,0,0},
            {0,1,0,0,7,0,0,0,6},
            {0,0,3,2,0,0,0,8,0},
            {0,6,0,5,0,0,0,0,9},
            {0,0,4,0,0,0,0,3,0},
            {0,0,0,0,0,9,7,0,0}
        };

        SudokuSolver solver = new SudokuSolver(puzzle);
        System.out.println("=== 数独求解器 ===");
        System.out.println("原始题目：");
        solver.printBoard();

        long t0 = System.currentTimeMillis();
        boolean ok = solver.solve();
        long t1 = System.currentTimeMillis();

        System.out.println("\n求解结果：" + (ok ? "成功" : "失败"));
        System.out.println("搜索步数: " + solver.steps);
        System.out.println("耗时: " + (t1-t0) + "ms\n");
        solver.printBoard();
    }
}

算法对比

本文实现的三项优化叠加，使求解效率提升4个数量级。

位运算技巧

候选集用位掩码存储带来巨大性能收益：

int candidates = 0x3FE; // 1-9均可: 二进制 1111111110

// 检查v是否为候选
boolean isCandidate = (candidates & (1 << v)) != 0;

// 从候选集中删除v
candidates &= ~(1 << v);

// 统计候选数个数
int count = Integer.bitCount(candidates >> 1);

位运算在JVM中被编译为单条CPU指令，比List/Set操作快10倍以上。

复杂度分析

总结

本文用Java实现了高性能数独求解器，核心在于约束传播与回溯的深度融合：

1. MRV启发：优先处理候选最少的变量，尽早暴露矛盾分支
2. 前向检查：赋值后立即传播约束，避免深入无效子树
3. 单值传播：自动确定必然值并级联触发，大量减少搜索
4. 位运算优化：候选集用位掩码表示，内存紧凑、操作极快

读者可继续探索：实现裸对/隐藏对（Naked/Hidden Pair）进一步剪枝，或将求解器扩展为数独生成器（先生成完整解再挖洞，确保唯一解）。