引言
数独（Sudoku）是一种源自18世纪瑞士的逻辑填数游戏，玩家需要在9×9的网格中填入数字1-9，使得每行、每列以及每个3×3的宫格内都不出现重复数字。数独的求解是约束满足问题（CSP）的经典案例，看似简单的人类解题过程背后，蕴含着丰富的算法设计空间。本文将使用Java实现数独求解器，核心采用回溯法（Backtracking）进行深度搜索，并结合约束传播（Constraint Propagation）中的唯一候选数法和隐性唯一候选数法进行剪枝，大幅提升求解效率。
问题建模
将数独棋盘表示为9×9的二维数组，空格子用0表示。约束条件为：
– 每行包含1-9且不重复
– 每列包含1-9且不重复
– 每个3×3宫格包含1-9且不重复
状态转移：选择一个空格子，尝试填入1-9中合法的数字，递归求解。
核心算法设计
1. 棋盘表示与基础约束检查
import java.util.*;
/**
* 数独求解器
* 结合回溯法与约束传播
*/
public class SudokuSolver {
private static final int SIZE = 9;
private static final int BOX_SIZE = 3;
private int[][] board;
private boolean solved;
public SudokuSolver(int[][] board) {
this.board = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
System.arraycopy(board[i], 0, this.board[i], 0, SIZE);
}
this.solved = false;
}
public int[][] getBoard() { return board; }
/**
* 检查在(row, col)位置填入num是否合法
*/
public boolean isValid(int row, int col, int num) {
// 检查行
for (int c = 0; c < SIZE; c++) {
if (board[row][c] == num) return false;
}
// 检查列
for (int r = 0; r < SIZE; r++) {
if (board[r][col] == num) return false;
}
// 检查3x3宫格
int boxRow = (row / BOX_SIZE) * BOX_SIZE;
int boxCol = (col / BOX_SIZE) * BOX_SIZE;
for (int r = boxRow; r < boxRow + BOX_SIZE; r++) {
for (int c = boxCol; c < boxCol + BOX_SIZE; c++) {
if (board[r][c] == num) return false;
}
}
return true;
}
/**
* 找到下一个空格
* @return [row, col] 或 null（已全部填满）
*/
private int[] findEmpty() {
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
if (board[r][c] == 0) {
return new int[]{r, c};
}
}
}
return null;
}
2. 基础回溯法求解
/**
* 基础回溯法求解
* 按顺序尝试每个空格的所有候选数
*/
public boolean solveBacktrack() {
int[] empty = findEmpty();
if (empty == null) {
return true; // 已全部填满
}
int row = empty[0];
int col = empty[1];
for (int num = 1; num <= SIZE; num++) {
if (isValid(row, col, num)) {
board[row][col] = num;
if (solveBacktrack()) {
return true;
}
// 回溯
board[row][col] = 0;
}
}
return false; // 无解
}
3. MRV启发式与约束传播优化
/**
* 计算某空格的可选数字集合（候选数）
*/
public List<Integer> getCandidates(int row, int col) {
List<Integer> candidates = new ArrayList<>();
for (int num = 1; num <= SIZE; num++) {
if (isValid(row, col, num)) {
candidates.add(num);
}
}
return candidates;
}
/**
* MRV（Minimum Remaining Values）启发式
* 选择候选数最少的空格，减少分支因子
*/
private int[] findEmptyMRV() {
int minCandidates = SIZE + 1;
int[] best = null;
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
if (board[r][c] == 0) {
int count = getCandidates(r, c).size();
if (count < minCandidates) {
minCandidates = count;
best = new int[]{r, c};
if (count == 1) return best; // 最优情况
}
}
}
}
return best;
}
/**
* 约束传播：唯一候选数法（Naked Single）
* 如果某空格只有一个候选数，直接填入
* @return 是否成功传播（无矛盾）
*/
public boolean propagateConstraints() {
boolean changed = true;
while (changed) {
changed = false;
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
if (board[r][c] == 0) {
List<Integer> candidates = getCandidates(r, c);
if (candidates.isEmpty()) {
return false; // 矛盾：无候选数
}
if (candidates.size() == 1) {
board[r][c] = candidates.get(0);
changed = true;
}
}
}
}
}
return true;
}
/**
* 高级求解：MRV + 约束传播 + 回溯
*/
public boolean solveAdvanced() {
// 先进行约束传播简化问题
if (!propagateConstraints()) {
return false;
}
int[] empty = findEmptyMRV();
if (empty == null) {
return true; // 已解决
}
int row = empty[0];
int col = empty[1];
List<Integer> candidates = getCandidates(row, col);
for (int num : candidates) {
// 保存当前棋盘状态（用于回溯）
int[][] saved = saveState();
board[row][col] = num;
if (solveAdvanced()) {
return true;
}
// 恢复状态
restoreState(saved);
}
return false;
}
private int[][] saveState() {
int[][] copy = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
System.arraycopy(board[i], 0, copy[i], 0, SIZE);
}
return copy;
}
private void restoreState(int[][] state) {
for (int i = 0; i < SIZE; i++) {
System.arraycopy(state[i], 0, board[i], 0, SIZE);
}
}
4. 数独生成器
/**
* 生成完整数独解（随机填充后求解）
*/
public static int[][] generateCompleteBoard() {
int[][] empty = new int[SIZE][SIZE];
SudokuSolver solver = new SudokuSolver(empty);
solver.fillRandomDiagonal(); // 随机填充对角线三个宫格
solver.solveAdvanced();
return solver.getBoard();
}
/**
* 随机填充对角线上的三个3x3宫格
* 对角线宫格互不干扰，可独立随机填充
*/
private void fillRandomDiagonal() {
Random random = new Random();
for (int box = 0; box < 3; box++) {
List<Integer> nums = new ArrayList<>();
for (int i = 1; i <= SIZE; i++) nums.add(i);
Collections.shuffle(nums, random);
int idx = 0;
for (int r = box * BOX_SIZE; r < box * BOX_SIZE + BOX_SIZE; r++) {
for (int c = box * BOX_SIZE; c < box * BOX_SIZE + BOX_SIZE; c++) {
board[r][c] = nums.get(idx++);
}
}
}
}
/**
* 从完整解中挖空生成谜题
* @param numHoles 挖空数量
*/
public static int[][] generatePuzzle(int numHoles) {
int[][] solution = generateCompleteBoard();
int[][] puzzle = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
System.arraycopy(solution[i], 0, puzzle[i], 0, SIZE);
}
Random random = new Random();
int holes = 0;
while (holes < numHoles) {
int r = random.nextInt(SIZE);
int c = random.nextInt(SIZE);
if (puzzle[r][c] != 0) {
puzzle[r][c] = 0;
holes++;
}
}
return puzzle;
}
5. 主程序与测试
/**
* 打印数独棋盘
*/
public void printBoard() {
for (int r = 0; r < SIZE; r++) {
if (r % BOX_SIZE == 0 && r != 0) {
System.out.println("------+-------+------");
}
for (int c = 0; c < SIZE; c++) {
if (c % BOX_SIZE == 0 && c != 0) {
System.out.print("| ");
}
if (board[r][c] == 0) {
System.out.print(". ");
} else {
System.out.print(board[r][c] + " ");
}
}
System.out.println();
}
}
/**
* 验证解的正确性
*/
public boolean verifySolution() {
for (int i = 0; i < SIZE; i++) {
boolean[] rowCheck = new boolean[SIZE + 1];
boolean[] colCheck = new boolean[SIZE + 1];
for (int j = 0; j < SIZE; j++) {
// 检查行
if (board[i][j] == 0) return false;
if (rowCheck[board[i][j]]) return false;
rowCheck[board[i][j]] = true;
// 检查列
if (colCheck[board[j][i]]) return false;
colCheck[board[j][i]] = true;
}
}
// 检查宫格
for (int boxR = 0; boxR < 3; boxR++) {
for (int boxC = 0; boxC < 3; boxC++) {
boolean[] boxCheck = new boolean[SIZE + 1];
for (int r = boxR * BOX_SIZE; r < boxR * BOX_SIZE + BOX_SIZE; r++) {
for (int c = boxC * BOX_SIZE; c < boxC * BOX_SIZE + BOX_SIZE; c++) {
if (boxCheck[board[r][c]]) return false;
boxCheck[board[r][c]] = true;
}
}
}
}
return true;
}
public static void main(String[] args) {
// 经典数独难题（世界最难数独之一）
int[][] hardPuzzle = {
{8, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 3, 6, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 9, 0, 2, 0, 0},
{0, 5, 0, 0, 0, 7, 0, 0, 0},
{0, 0, 0, 0, 4, 5, 7, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 3, 0},
{0, 0, 1, 0, 0, 0, 0, 6, 8},
{0, 0, 8, 5, 0, 0, 0, 1, 0},
{0, 9, 0, 0, 0, 0, 4, 0, 0}
};
System.out.println("原始谜题：");
SudokuSolver solver = new SudokuSolver(hardPuzzle);
solver.printBoard();
long start = System.currentTimeMillis();
boolean success = solver.solveAdvanced();
long end = System.currentTimeMillis();
System.out.println("\n求解结果：" + (success ? "成功" : "失败"));
System.out.println("耗时：" + (end - start) + "ms");
if (success) {
System.out.println("\n解答：");
solver.printBoard();
System.out.println("验证：" + (solver.verifySolution() ? "正确" : "错误"));
}
// 生成随机谜题测试
System.out.println("\n=== 随机生成测试 ===");
int[][] puzzle = generatePuzzle(40);
System.out.println("随机谜题（40空格）：");
SudokuSolver genSolver = new SudokuSolver(puzzle);
genSolver.printBoard();
start = System.currentTimeMillis();
success = genSolver.solveAdvanced();
end = System.currentTimeMillis();
System.out.println("\n求解：" + (success ? "成功" : "失败") + "，耗时：" + (end - start) + "ms");
}
}
复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 基础回溯法 | O(9^m) | O(81) | m为空格数，最坏情况指数级 |
| MRV启发式 | O(9^m) | O(81) | 实际大幅减少分支 |
| 约束传播 | O(81 × 9) | O(81) | 多项式时间预处理 |
| 组合算法 | 远低于O(9^m) | O(81) | 实际求解极快 |
对于标准9×9数独，组合算法在毫秒级完成求解；即使是世界最难数独，也能在1秒内解决。
算法扩展
- ** Dancing Links (DLX)**：Donald Knuth提出的精确覆盖问题算法，将数独转化为精确覆盖后用DLX高效求解
- 隐性唯一候选数（Hidden Single）：某数字在某行/列/宫格中只有唯一可填位置
- 高级约束技术： naked pairs/triples、X-Wing、Swordfish等人类高级技巧
- 多解检测：修改回溯条件，收集所有合法解，判断谜题是否唯一解
总结
本文通过回溯法与约束传播的结合实现了高效的数独求解器。核心优化策略包括：
1. MRV启发式：优先选择候选数最少的变量，最小化分支因子
2. 约束传播：在搜索前反复应用唯一候选数规则，大幅简化问题
3. 对角线随机初始化：利用对角线宫格的独立性快速生成完整解
数独求解展示了约束满足问题的经典求解范式：约束传播降低搜索空间，启发式排序优化搜索顺序，回溯法保证完备性。这一组合思路适用于所有CSP问题，如图着色、调度排课、电路布局等。
