游戏介绍
数独（Sudoku）是一种逻辑填数游戏，在9×9的方格中填入1-9的数字，要求每行、每列以及每个3×3的宫格内数字均不重复。本文用Java实现数独求解器，核心使用回溯算法配合约束传播（MRV启发式）高效剪枝。
核心算法
回溯算法（Backtracking）
深度优先搜索尝试每个空格的所有可能数字，一旦发现矛盾则回溯。基础回溯即可解决大多数数独，但效率较低。
MRV启发式（Minimum Remaining Values）
每次选择候选数字最少的空格进行填充，最大化剪枝效果。配合前向检查（Forward Checking），在赋值后立即更新相关单元格的候选集。
约束传播
通过维护每个空格的可选值集合，当某单元格只剩一个候选值时自动确定（单元传播），连锁触发更多确定，大幅减少搜索分支。
Java实现
import java.util.*;
public class SudokuSolver {
static final int SIZE = 9;
static final int BOX = 3;
// 示例谜题（0表示空格）
static final int[][] PUZZLE = {
{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}
};
int[][] board = new int[SIZE][SIZE];
// 每个格子的候选值集合
List<Set<Integer>> candidates = new ArrayList<>();
int steps = 0;
public SudokuSolver() {
for (int y = 0; y < SIZE; y++) {
System.arraycopy(PUZZLE[y], 0, board[y], 0, SIZE);
}
initCandidates();
}
// 初始化候选值
void initCandidates() {
for (int i = 0; i < SIZE * SIZE; i++) {
candidates.add(new HashSet<>());
}
for (int y = 0; y < SIZE; y++) {
for (int x = 0; x < SIZE; x++) {
if (board[y][x] == 0) {
candidates.get(idx(x, y)).addAll(getCandidates(x, y));
}
}
}
}
int idx(int x, int y) { return y * SIZE + x; }
// 计算某空格的所有合法候选值
Set<Integer> getCandidates(int x, int y) {
Set<Integer> nums = new HashSet<>();
for (int i = 1; i <= SIZE; i++) nums.add(i);
// 移除行中已有的数字
for (int cx = 0; cx < SIZE; cx++) {
if (board[y][cx] != 0) nums.remove(board[y][cx]);
}
// 移除列中已有的数字
for (int cy = 0; cy < SIZE; cy++) {
if (board[cy][x] != 0) nums.remove(board[cy][x]);
}
// 移除3x3宫中已有的数字
int bx = (x / BOX) * BOX, by = (y / BOX) * BOX;
for (int dy = 0; dy < BOX; dy++) {
for (int dx = 0; dx < BOX; dx++) {
int val = board[by + dy][bx + dx];
if (val != 0) nums.remove(val);
}
}
return nums;
}
// MRV：找到候选值最少的空格
int[] findMRV() {
int minCount = SIZE + 1;
int[] best = null;
for (int y = 0; y < SIZE; y++) {
for (int x = 0; x < SIZE; x++) {
if (board[y][x] == 0) {
int count = candidates.get(idx(x, y)).size();
if (count < minCount) {
minCount = count;
best = new int[]{x, y};
if (count == 1) return best; // 无法更优
}
}
}
}
return best;
}
// 回溯求解
boolean solve() {
int[] mrv = findMRV();
if (mrv == null) return true; // 全部填满
int x = mrv[0], y = mrv[1];
Set<Integer> opts = new HashSet<>(candidates.get(idx(x, y)));
for (int val : opts) {
steps++;
// 保存状态用于回溯
Map<Integer, Set<Integer>> changed = new HashMap<>();
// 放置数字
board[y][x] = val;
candidates.get(idx(x, y)).clear();
// 更新约束：行、列、宫
boolean valid = true;
List<int[]> toUpdate = new ArrayList<>();
for (int cx = 0; cx < SIZE; cx++) {
if (cx != x && board[y][cx] == 0) toUpdate.add(new int[]{cx, y});
}
for (int cy = 0; cy < SIZE; cy++) {
if (cy != y && board[cy][x] == 0) toUpdate.add(new int[]{x, cy});
}
int bx = (x / BOX) * BOX, by = (y / BOX) * BOX;
for (int dy = 0; dy < BOX; dy++) {
for (int dx = 0; dx < BOX; dx++) {
int nx = bx + dx, ny = by + dy;
if ((nx != x || ny != y) && board[ny][nx] == 0) {
toUpdate.add(new int[]{nx, ny});
}
}
}
for (int[] p : toUpdate) {
int pi = idx(p[0], p[1]);
Set<Integer> cands = candidates.get(pi);
if (cands.contains(val)) {
if (!changed.containsKey(pi)) {
changed.put(pi, new HashSet<>(cands));
}
cands.remove(val);
if (cands.isEmpty()) {
valid = false; // 约束冲突
break;
}
}
}
// 单元传播：检查是否有唯一候选值的格子
if (valid) {
Queue<int[]> queue = new LinkedList<>();
for (int[] p : toUpdate) {
if (candidates.get(idx(p[0], p[1])).size() == 1) {
queue.add(p);
}
}
while (!queue.isEmpty() && valid) {
int[] p = queue.poll();
if (board[p[1]][p[0]] != 0) continue;
Set<Integer> c = candidates.get(idx(p[0], p[1]));
if (c.size() != 1) continue;
int v = c.iterator().next();
// 递归赋值（简化：仅检查是否合法）
board[p[1]][p[0]] = v;
c.clear();
// 继续传播...
}
}
if (valid && solve()) return true;
// 回溯
board[y][x] = 0;
for (Map.Entry<Integer, Set<Integer>> e : changed.entrySet()) {
candidates.set(e.getKey(), e.getValue());
}
// 恢复被单元传播赋值的格子
for (int[] p : toUpdate) {
if (board[p[1]][p[0]] != 0 && PUZZLE[p[1]][p[0]] == 0) {
// 检查是否是本次传播赋值的
boolean fromPuzzle = false;
for (int py = 0; py < SIZE; py++) {
for (int px = 0; px < SIZE; px++) {
if (PUZZLE[py][px] != 0) {
// 保留原始谜题的值
}
}
}
}
}
// 简化的回溯：重新计算所有候选值
restoreCandidates();
}
return false;
}
// 从当前board重新计算所有候选值
void restoreCandidates() {
for (int i = 0; i < SIZE * SIZE; i++) {
candidates.get(i).clear();
}
for (int y = 0; y < SIZE; y++) {
for (int x = 0; x < SIZE; x++) {
if (board[y][x] == 0) {
candidates.get(idx(x, y)).addAll(getCandidates(x, y));
}
}
}
}
// 打印数独
void printBoard() {
for (int y = 0; y < SIZE; y++) {
if (y % BOX == 0 && y > 0) System.out.println("------+-------+------");
for (int x = 0; x < SIZE; x++) {
if (x % BOX == 0 && x > 0) System.out.print("| ");
int v = board[y][x];
System.out.print(v == 0 ? ". " : v + " ");
}
System.out.println();
}
}
// 验证解的正确性
boolean verify() {
for (int y = 0; y < SIZE; y++) {
Set<Integer> row = new HashSet<>();
for (int x = 0; x < SIZE; x++) {
if (board[y][x] == 0) return false;
if (!row.add(board[y][x])) return false;
}
}
for (int x = 0; x < SIZE; x++) {
Set<Integer> col = new HashSet<>();
for (int y = 0; y < SIZE; y++) {
if (!col.add(board[y][x])) return false;
}
}
for (int by = 0; by < SIZE; by += BOX) {
for (int bx = 0; bx < SIZE; bx += BOX) {
Set<Integer> box = new HashSet<>();
for (int dy = 0; dy < BOX; dy++) {
for (int dx = 0; dx < BOX; dx++) {
if (!box.add(board[by + dy][bx + dx])) return false;
}
}
}
}
return true;
}
public static void main(String[] args) {
SudokuSolver solver = new SudokuSolver();
System.out.println("原始谜题:");
solver.printBoard();
long start = System.currentTimeMillis();
boolean solved = solver.solve();
long end = System.currentTimeMillis();
System.out.println("\n解答:");
solver.printBoard();
System.out.println("求解成功: " + solved);
System.out.println("验证通过: " + solver.verify());
System.out.println("搜索步数: " + solver.steps);
System.out.println("耗时: " + (end - start) + "ms");
}
}
复杂度分析
- 基础回溯：最坏情况 $O(9^{81}) \approx O(10^{77})$，不实用
- MRV+约束传播：通过剪枝将实际复杂度降至 $O(10^4)$ 到 $O(10^6)$ 步
- 空间复杂度：$O(81 \times 9)$，存储每个格子的候选值集合
- ** Dancing Links（DLX）**：Donald Knuth提出的精确覆盖算法，可将数独转化为精确覆盖问题，求解效率更高
进阶方向
- DLX算法：将数独建模为精确覆盖问题，用舞蹈链数据结构高效求解
- 生成谜题：通过随机挖空并确保唯一解来生成数独题目
- 难度评级：基于求解所需回溯步数评估题目难度
总结
本文通过MRV启发式和约束传播大幅优化了数独回溯求解的效率。核心思路是”优先处理约束最强的变量”，这一策略在约束满足问题（CSP）中具有普适性。读者可以尝试实现更完善的单元传播和DLX算法，体验不同求解策略的差异。
