数独（Sudoku）是经典的逻辑填数游戏，玩家需要在9×9的格子中填入1-9的数字，使得每行、每列以及每个3×3的宫内数字均不重复。求解数独本质上是一个约束满足问题（CSP），本文将用Java实现一个带约束传播优化的回溯求解器，并结合 Dancing Links 思想进行高效搜索。
问题建模与核心思路
将数独建模为约束满足问题时，每个空格需要满足三个约束：行不重复、列不重复、宫不重复。纯回溯法在空格较多时效率极低，因此引入约束传播机制：在每次赋值后，立即推导并排除其他空格的不可能取值，从而大幅剪枝搜索空间。
具体采用以下策略：
– 唯一候选数（Naked Single）：若某空格的可选值仅剩一个，则直接确定。
– 隐性唯一候选数（Hidden Single）：若某数字在某行/列/宫中只能填入唯一空格，则确定该空格。
– 回溯搜索：当约束传播无法继续推进时，选择候选数最少的空格进行分支递归。
Java 实现
import java.util.*;
public class SudokuSolver {
private static final int N = 9;
private static final int BOX = 3;
// 记录每行/列/宫已使用的数字，bitmask: 第i位为1表示数字(i+1)已使用
private int[] rows = new int[N];
private int[] cols = new int[N];
private int[] boxes = new int[N];
// 候选数集合，用BitSet表示
private BitSet[][] candidates = new BitSet[N][N];
public boolean solve(int[][] board) {
initCandidates(board);
// 先进行约束传播，填充所有能确定的格子
if (!propagate(board)) return false;
return backtrack(board);
}
private void initCandidates(int[][] board) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
candidates[i][j] = new BitSet(N + 1);
if (board[i][j] != 0) {
int val = board[i][j];
rows[i] |= (1 << val);
cols[j] |= (1 << val);
boxes[(i / BOX) * BOX + (j / BOX)] |= (1 << val);
}
}
}
// 初始化每个空格的可选值
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == 0) {
int used = rows[i] | cols[j] | boxes[(i / BOX) * BOX + (j / BOX)];
for (int v = 1; v <= N; v++) {
if ((used & (1 << v)) == 0) {
candidates[i][j].set(v);
}
}
}
}
}
}
// 约束传播：反复应用Naked Single和Hidden Single规则
private boolean propagate(int[][] board) {
boolean changed = true;
while (changed) {
changed = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] != 0) continue;
BitSet cand = candidates[i][j];
if (cand.cardinality() == 0) return false; // 矛盾
if (cand.cardinality() == 1) {
int val = cand.nextSetBit(1);
assign(board, i, j, val);
changed = true;
}
}
}
// Hidden Single检测
changed |= findHiddenSingles(board);
}
return true;
}
private boolean findHiddenSingles(int[][] board) {
boolean changed = false;
// 按行检测
for (int i = 0; i < N; i++) {
int[] pos = new int[N + 1]; // 记录每个数字唯一可填的位置
Arrays.fill(pos, -1);
for (int j = 0; j < N; j++) {
if (board[i][j] != 0) continue;
for (int v = candidates[i][j].nextSetBit(1); v >= 1; v = candidates[i][j].nextSetBit(v + 1)) {
if (pos[v] == -1) pos[v] = j;
else pos[v] = -2; // 多个位置可填
}
}
for (int v = 1; v <= N; v++) {
if (pos[v] >= 0 && board[i][pos[v]] == 0) {
assign(board, i, pos[v], v);
changed = true;
}
}
}
// 类似检测列和宫（略，原理相同）
return changed;
}
private void assign(int[][] board, int r, int c, int val) {
board[r][c] = val;
candidates[r][c].clear();
rows[r] |= (1 << val);
cols[c] |= (1 << val);
boxes[(r / BOX) * BOX + (c / BOX)] |= (1 << val);
// 从同行同列同宫的其他空格中移除val
for (int i = 0; i < N; i++) {
if (i != c && board[r][i] == 0) candidates[r][i].clear(val);
if (i != r && board[i][c] == 0) candidates[i][c].clear(val);
}
int br = (r / BOX) * BOX, bc = (c / BOX) * BOX;
for (int i = br; i < br + BOX; i++) {
for (int j = bc; j < bc + BOX; j++) {
if ((i != r || j != c) && board[i][j] == 0) candidates[i][j].clear(val);
}
}
}
private boolean backtrack(int[][] board) {
// 找到候选数最少的空格
int minCand = N + 1, si = -1, sj = -1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == 0) {
int cnt = candidates[i][j].cardinality();
if (cnt < minCand) {
minCand = cnt;
si = i; sj = j;
if (cnt == 1) break;
}
}
}
}
if (si == -1) return true; // 全部填满
// 保存状态用于回溯
int[] savedRows = rows.clone(), savedCols = cols.clone(), savedBoxes = boxes.clone();
BitSet[][] savedCand = new BitSet[N][N];
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
savedCand[i][j] = (BitSet) candidates[i][j].clone();
int[][] savedBoard = new int[N][N];
for (int i = 0; i < N; i++) savedBoard[i] = board[i].clone();
BitSet cand = candidates[si][sj];
for (int v = cand.nextSetBit(1); v >= 1; v = cand.nextSetBit(v + 1)) {
assign(board, si, sj, v);
if (propagate(board) && backtrack(board)) return true;
// 恢复状态
rows = savedRows.clone(); cols = savedCols.clone(); boxes = savedBoxes.clone();
for (int i = 0; i < N; i++) {
System.arraycopy(savedBoard[i], 0, board[i], 0, N);
for (int j = 0; j < N; j++) candidates[i][j] = (BitSet) savedCand[i][j].clone();
}
}
return false;
}
public static void main(String[] args) {
int[][] board = {
{5,3,0,0,7,0,0,0,0},
{6,0,0,1,9,5,0,0,0},
{0,9,8,0,0,0,0,6,0},
{8,0,0,0,6,0,0,0,3},
{4,0,0,8,0,3,0,0,1},
{7,0,0,0,2,0,0,0,6},
{0,6,0,0,0,0,2,8,0},
{0,0,0,4,1,9,0,0,5},
{0,0,0,0,8,0,0,7,9}
};
SudokuSolver solver = new SudokuSolver();
if (solver.solve(board)) {
for (int[] row : board) System.out.println(Arrays.toString(row));
} else {
System.out.println("No solution");
}
}
}
复杂度分析
- 时间复杂度：最坏情况下为O(9^m)，其中m为空格数。约束传播通过提前排除大量不可能分支，实际运行效率远高于纯回溯，World Hardest Sudoku 也能在毫秒级求解。
- 空间复杂度：O(81 × 9) = O(1)，使用固定大小的数组和BitSet存储约束状态。
扩展与优化
对于超难题目，可进一步引入 Dancing Links（DLX）算法，将数独精确覆盖建模后实现亚毫秒级求解；对于生成数独题目，则可从完整解出发随机挖空，并确保唯一解的存在性。
