数独（Sudoku）是源自18世纪瑞士的经典逻辑填数游戏。玩家在9×9的格子中填入1-9的数字，满足每行、每列、每个3×3宫格均不重复。表面上看是简单的填数，背后却涉及约束满足问题（CSP）、约束传播（Constraint Propagation）与回溯搜索（Backtracking）三大算法支柱。本文将用Java完整实现一个带智能提示的数独求解器，从候选数管理到链式约束排除逐层剖析。
一、数独的约束满足问题建模
1.1 为什么用CSP视角
标准数独有81个变量（格子），每个变量的取值域为{1,2,…,9}。约束条件包括：
– 行约束：同一行9个格子取值互异
– 列约束：同一列9个格子取值互异
– 宫约束：同一3×3宫格内9个格子取值互异
这种”变量-取值域-约束”的三元组结构，天然适合用约束满足问题框架求解。与暴力回溯相比，约束传播能在搜索前大量剪枝，将搜索空间压缩数个数量级。
1.2 核心数据结构：候选数集合
每个格子维护一个候选数集合（Bitmask实现），表示当前仍可行的数字：
/**
* 数独格子：维护候选数集合的位掩码表示
* 第i位为1表示数字(i+1)仍可行，例如bitmask=0b101表示候选数{1,3}
*/
class Cell {
// 格子值，0表示未填
int value;
// 候选数位掩码，9位分别对应数字1-9
int candidates;
// 已确定数值时candidates=0
boolean fixed;
Cell() {
this.value = 0;
this.candidates = 0b111111111; // 初始时1-9均可
this.fixed = false;
}
/**
* 设置确定值，清空候选数
*/
void setValue(int v) {
this.value = v;
this.candidates = 0;
this.fixed = true;
}
/**
* 从候选数中移除指定数字
* @return 如果候选数发生变化返回true
*/
boolean eliminate(int num) {
int mask = 1 << (num - 1);
if ((candidates & mask) != 0) {
candidates &= ~mask;
return true;
}
return false;
}
/**
* 获取当前候选数数量
*/
int candidateCount() {
return Integer.bitCount(candidates);
}
/**
* 获取唯一的候选数（当candidateCount==1时有效）
*/
int getOnlyCandidate() {
return Integer.numberOfTrailingZeros(candidates) + 1;
}
/**
* 检查候选数中是否包含某数字
*/
boolean hasCandidate(int num) {
return (candidates & (1 << (num - 1))) != 0;
}
@Override
public String toString() {
return fixed ? String.valueOf(value) : ".";
}
}
1.3 数独棋盘整体结构
/**
* 数独棋盘：9×9格子 + 约束传播引擎
*/
class SudokuBoard {
static final int SIZE = 9;
static final int BOX_SIZE = 3;
private final Cell[][] cells;
// 用于快速定位同行/同列/同宫的格子索引
private final List<int[]>[] rowCells; // 每行包含的格子坐标
private final List<int[]>[] colCells; // 每列包含的格子坐标
private final List<int[]>[] boxCells; // 每宫包含的格子坐标
@SuppressWarnings("unchecked")
SudokuBoard() {
cells = new Cell[SIZE][SIZE];
rowCells = new ArrayList[SIZE];
colCells = new ArrayList[SIZE];
boxCells = new ArrayList[SIZE];
for (int i = 0; i < SIZE; i++) {
rowCells[i] = new ArrayList<>();
colCells[i] = new ArrayList<>();
boxCells[i] = new ArrayList<>();
}
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
cells[r][c] = new Cell();
rowCells[r].add(new int[]{r, c});
colCells[c].add(new int[]{r, c});
int boxIdx = (r / BOX_SIZE) * BOX_SIZE + (c / BOX_SIZE);
boxCells[boxIdx].add(new int[]{r, c});
}
}
}
/**
* 从字符串加载数独（81个字符，'.'或'0'表示空格）
*/
void loadFromString(String puzzle) {
for (int i = 0; i < 81; i++) {
char ch = puzzle.charAt(i);
int r = i / SIZE, c = i % SIZE;
if (ch >= '1' && ch <= '9') {
cells[r][c].setValue(ch - '0');
}
}
}
Cell getCell(int r, int c) {
return cells[r][c];
}
/**
* 获取指定格子所属宫格的索引
*/
static int boxIndex(int r, int c) {
return (r / BOX_SIZE) * BOX_SIZE + (c / BOX_SIZE);
}
boolean isSolved() {
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
if (cells[r][c].value == 0) return false;
}
}
return true;
}
/**
* 打印当前棋盘状态
* 已填数字显示数字，未填显示候选数数量提示
*/
void printBoard() {
for (int r = 0; r < SIZE; r++) {
if (r > 0 && r % BOX_SIZE == 0) {
System.out.println("------+-------+------");
}
for (int c = 0; c < SIZE; c++) {
if (c > 0 && c % BOX_SIZE == 0) System.out.print("| ");
Cell cell = cells[r][c];
System.out.print(cell.fixed ? cell.value : ".");
System.out.print(" ");
}
System.out.println();
}
}
/**
* 深拷贝棋盘（用于回溯时保存状态）
*/
SudokuBoard deepCopy() {
SudokuBoard copy = new SudokuBoard();
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
Cell src = this.cells[r][c];
Cell dst = copy.cells[r][c];
dst.value = src.value;
dst.candidates = src.candidates;
dst.fixed = src.fixed;
}
}
return copy;
}
}
二、核心算法一：约束传播引擎
2.1 初始约束传播
当棋盘上已有一些预设数字时，首先需要将这些信息传播到相关格子的候选数中：
/**
* 约束传播引擎：负责维护候选数集合的一致性
*/
class ConstraintPropagator {
private final SudokuBoard board;
// 传播队列：存储刚被确定的格子坐标，触发周边候选数更新
private final ArrayDeque<int[]> propagationQueue;
ConstraintPropagator(SudokuBoard board) {
this.board = board;
this.propagationQueue = new ArrayDeque<>();
}
/**
* 执行完整的初始约束传播
* 步骤：
* 1. 将所有预设数字加入传播队列
* 2. 循环处理队列：对刚确定的数字，从同行/同列/同宫格子中消除该候选数
* 3. 若某格子候选数减为1，自动确定其值并加入队列继续传播
* @return 如果传播过程中发现矛盾（某格子候选数为空）返回false
*/
boolean propagateAll() {
// 初始化：将所有已填数字加入传播队列
for (int r = 0; r < SudokuBoard.SIZE; r++) {
for (int c = 0; c < SudokuBoard.SIZE; c++) {
Cell cell = board.getCell(r, c);
if (cell.fixed) {
propagationQueue.add(new int[]{r, c});
}
}
}
return processQueue();
}
/**
* 处理传播队列，直到队列为空
*/
private boolean processQueue() {
while (!propagationQueue.isEmpty()) {
int[] pos = propagationQueue.poll();
int r = pos[0], c = pos[1];
Cell cell = board.getCell(r, c);
int val = cell.value;
// 从同行消除
for (int[] rc : board.rowCells[r]) {
if (rc[0] == r && rc[1] == c) continue;
if (!eliminateCandidate(rc[0], rc[1], val)) return false;
}
// 从同列消除
for (int[] rc : board.colCells[c]) {
if (rc[0] == r && rc[1] == c) continue;
if (!eliminateCandidate(rc[0], rc[1], val)) return false;
}
// 从同宫消除
int boxIdx = SudokuBoard.boxIndex(r, c);
for (int[] rc : board.boxCells[boxIdx]) {
if (rc[0] == r && rc[1] == c) continue;
if (!eliminateCandidate(rc[0], rc[1], val)) return false;
}
}
return true;
}
/**
* 从指定格子消除候选数num
* 如果消除后候选数唯一，自动赋值并加入传播队列
* @return false表示出现矛盾（候选数为空）
*/
private boolean eliminateCandidate(int r, int c, int num) {
Cell cell = board.getCell(r, c);
if (cell.fixed) return true; // 已确定，无需处理
boolean changed = cell.eliminate(num);
if (!changed) return true;
// 矛盾检测：候选数为空
if (cell.candidates == 0) {
return false; // 约束冲突
}
// 唯余法（Naked Single）：候选数只剩一个，自动确定
if (cell.candidateCount() == 1) {
int onlyVal = cell.getOnlyCandidate();
cell.setValue(onlyVal);
propagationQueue.add(new int[]{r, c});
}
return true;
}
}
2.2 隐单法（Hidden Single）
除了唯余法（某格子只剩一个候选数），还有更强的隐单法：在某行/列/宫中，某个数字只能出现在一个格子的候选数中，则该格子必为该数字：
/**
* 隐单法检测：在某约束单元中，某数字仅出现在一个格子的候选数中
*/
class HiddenSingleFinder {
private final SudokuBoard board;
HiddenSingleFinder(SudokuBoard board) {
this.board = board;
}
/**
* 在整个棋盘扫描隐单，直到没有新的隐单被发现
* @return 如果找到并设置了隐单返回true（表示需要继续传播）
*/
boolean findAndApplyHiddenSingles() {
boolean progress = false;
boolean changed;
do {
changed = false;
// 扫描所有行
for (int i = 0; i < SudokuBoard.SIZE; i++) {
if (scanUnit(board.rowCells[i])) changed = true;
}
// 扫描所有列
for (int i = 0; i < SudokuBoard.SIZE; i++) {
if (scanUnit(board.colCells[i])) changed = true;
}
// 扫描所有宫
for (int i = 0; i < SudokuBoard.SIZE; i++) {
if (scanUnit(board.boxCells[i])) changed = true;
}
if (changed) progress = true;
} while (changed);
return progress;
}
/**
* 扫描一个约束单元（行/列/宫），查找隐单
* @return 如果找到并应用了隐单返回true
*/
private boolean scanUnit(List<int[]> unitCells) {
boolean changed = false;
// 对每个数字1-9，统计在哪些未填格子的候选数中出现
for (int num = 1; num <= 9; num++) {
int count = 0;
int[] targetPos = null;
for (int[] rc : unitCells) {
Cell cell = board.getCell(rc[0], rc[1]);
if (cell.fixed && cell.value == num) {
count = -1; // 该数字已存在，跳过
break;
}
if (!cell.fixed && cell.hasCandidate(num)) {
count++;
targetPos = rc;
}
}
// 隐单发现：某数字恰好只在一个未填格子的候选数中
if (count == 1 && targetPos != null) {
Cell target = board.getCell(targetPos[0], targetPos[1]);
if (!target.fixed) {
target.setValue(num);
changed = true;
}
}
}
return changed;
}
}
三、核心算法二：约束传播驱动的回溯求解
3.1 求解器主框架
将约束传播与回溯结合：每次赋值前先进行完整的约束传播，大幅剪枝搜索空间：
/**
* 数独求解器：约束传播 + 隐单法 + 回溯搜索
*/
class SudokuSolver {
private int searchCount; // 统计搜索节点数，用于评估剪枝效果
SudokuBoard solve(SudokuBoard original) {
searchCount = 0;
SudokuBoard board = original.deepCopy();
// 第一阶段：约束传播
ConstraintPropagator propagator = new ConstraintPropagator(board);
if (!propagator.propagateAll()) {
return null; // 初始约束矛盾，无解
}
// 第二阶段：隐单法
HiddenSingleFinder hsFinder = new HiddenSingleFinder(board);
if (hsFinder.findAndApplyHiddenSingles()) {
// 隐单产生新确定值，需要再次约束传播
ConstraintPropagator cp2 = new ConstraintPropagator(board);
if (!cp2.propagateAll()) return null;
}
// 第三阶段：回溯搜索（带MRV启发式）
SudokuBoard result = backtrack(board);
System.out.println("搜索节点数: " + searchCount);
return result;
}
/**
* 回溯搜索，采用MRV（Minimum Remaining Values）启发式：
* 优先选择候选数最少的格子进行尝试，最大化剪枝效率
*/
private SudokuBoard backtrack(SudokuBoard board) {
if (board.isSolved()) return board;
// MRV：找到候选数最少且大于0的未填格子
int[] mrvPos = findMRV(board);
if (mrvPos == null) return null; // 有未填格子但无候选数，死路
int r = mrvPos[0], c = mrvPos[1];
Cell cell = board.getCell(r, c);
int candidates = cell.candidates;
// 按候选数从小到大尝试（排序启发式）
List<Integer> candList = new ArrayList<>();
for (int num = 1; num <= 9; num++) {
if ((candidates & (1 << (num - 1))) != 0) {
candList.add(num);
}
}
for (int num : candList) {
searchCount++;
SudokuBoard copy = board.deepCopy();
Cell copyCell = copy.getCell(r, c);
copyCell.setValue(num);
// 赋值后立即进行约束传播
ConstraintPropagator cp = new ConstraintPropagator(copy);
if (!cp.propagateAll()) continue; // 传播出现矛盾，剪枝
// 隐单法再次应用
HiddenSingleFinder hs = new HiddenSingleFinder(copy);
if (hs.findAndApplyHiddenSingles()) {
ConstraintPropagator cp2 = new ConstraintPropagator(copy);
if (!cp2.propagateAll()) continue;
}
SudokuBoard result = backtrack(copy);
if (result != null) return result;
}
return null; // 所有候选数尝试失败
}
/**
* MRV启发式：找到候选数最少（且大于0）的未填格子
* @return [row, col] 或 null（如果没有未填格子或矛盾）
*/
private int[] findMRV(SudokuBoard board) {
int minCandidates = 10;
int[] bestPos = null;
for (int r = 0; r < SudokuBoard.SIZE; r++) {
for (int c = 0; c < SudokuBoard.SIZE; c++) {
Cell cell = board.getCell(r, c);
if (!cell.fixed) {
int count = cell.candidateCount();
if (count == 0) return null; // 矛盾
if (count < minCandidates) {
minCandidates = count;
bestPos = new int[]{r, c};
}
}
}
}
return bestPos;
}
}
3.2 完整可运行的主程序
import java.util.*;
/**
* 数独求解器主程序
* 演示约束传播 + 隐单法 + MRV回溯的完整求解流程
*/
public class SudokuSolverApp {
public static void main(String[] args) {
// 世界最难数独之一（由芬兰数学家Arto Inkala设计）
String hardPuzzle =
"800000000" +
"003600000" +
"070090200" +
"050007000" +
"000045700" +
"000100030" +
"001000068" +
"008500010" +
"090000400";
// 中等难度数独
String mediumPuzzle =
"530070000" +
"600195000" +
"098000060" +
"800060003" +
"400803001" +
"700020006" +
"060000280" +
"000419005" +
"000080079";
System.out.println("=== 数独约束传播求解器 ===\n");
// 求解中等难度
System.out.println("【中等难度数独】");
solveAndDisplay(mediumPuzzle);
System.out.println("\n【世界最难数独】");
solveAndDisplay(hardPuzzle);
}
static void solveAndDisplay(String puzzle) {
SudokuBoard board = new SudokuBoard();
board.loadFromString(puzzle);
System.out.println("原始题目：");
board.printBoard();
long start = System.currentTimeMillis();
SudokuSolver solver = new SudokuSolver();
SudokuBoard solution = solver.solve(board);
long elapsed = System.currentTimeMillis() - start;
if (solution != null) {
System.out.println("\n求解结果：");
solution.printBoard();
System.out.println("耗时: " + elapsed + "ms");
} else {
System.out.println("无解！");
}
}
}
四、关键算法详解
4.1 位掩码的候选数管理
本文使用9位整数表示候选数集合，相比HashSet<Integer>或boolean[]有显著优势：
– 空间：每个格子仅需1个int（4字节），而非9个boolean或对象引用
– 速度：消除候选数是单次位运算&= ~mask，O(1)时间
– 计数：Integer.bitCount()由JVM intrinsic优化，底层用CPU指令POPCNT
初始候选数: 0b111111111 = 511 (数字1-9均可)
消除数字3后: 0b111110111 = 503 (第3位置0)
只剩数字5: 0b000010000 = 16 (可直接确定)
4.2 MRV启发式的剪枝威力
最小剩余值（Minimum Remaining Values）启发式优先选择候选数最少的变量，其直觉是：约束最多的变量最容易导致失败，越早尝试它越早发现死路。
以世界最难数独为例：
– 纯回溯（无约束传播）：搜索节点数可达数百万
– 约束传播 + MRV：搜索节点数通常降至数百甚至数十
– 加入隐单法后，许多数独可零回溯直接求解
4.3 约束传播与回溯的关系
两者形成互补的求解策略：
– 约束传播是”推理”：通过逻辑推导直接确定某些格子的值，无需猜测
– 回溯搜索是”猜测”：当推理无法继续时，对某个格子进行假设赋值
高效求解器的核心在于让约束传播尽可能多做工作，减少回溯次数。本文实现的求解器在每次赋值后都触发完整传播，确保搜索树极度瘦削。
五、算法复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 候选数消除（单次） | O(1) | O(1) | 位运算操作 |
| 约束传播（一轮） | O(81×9) | O(81) | 每个格子最多消除9次 |
| 隐单法扫描 | O(27×9×9) | O(1) | 27个单元×9数字×9格子 |
| MRV选择 | O(81) | O(1) | 遍历所有格子 |
| 回溯搜索最坏情况 | O(9^81) | O(81×深度) | 理论上限，实际远小于此 |
| 实际中等难度 | <1ms | O(81) | 约束传播后几乎零回溯 |
对于合法数独题目（唯一解），约束传播通常能直接解决60%-90%的格子，剩余格子的搜索空间已被极度压缩。
六、扩展方向
- 高级约束技巧：实现唯一矩形（Unique Rectangle）、X-Wing、Swordfish等高级模式，进一步提升无回溯求解率
- 多解检测：修改回溯逻辑，收集所有解而非找到第一个就返回，检测题目是否有唯一解
- 数独生成为NP问题：通过随机挖空+唯一解验证生成不同难度数独，挖空策略可用随机+回溯验证
- 并行求解：对不同分支赋值进行多线程并行回溯，利用现代CPU多核优势
- 可视化求解过程：用Swing/JavaFX展示约束传播过程中候选数的逐步消减动画
- 难度评估算法：基于求解过程中约束传播轮数、回溯节点数、高级技巧使用次数综合评分
七、总结
数独是理解约束满足问题的绝佳入门项目。本文实现的约束传播引擎通过位掩码候选数管理、队列驱动的链式消除、隐单法推理与MRV回溯四大技术组合，将数独求解从指数级暴力搜索优化到毫秒级响应。掌握这些基础后，你可以进一步学习SMT求解器、CSP求解框架（如Choco、JaCoP），向更复杂的调度、配置、规划问题迈进。
