LeetCode 37.解数独：回溯法在二维网格中的应用与剪枝策略-EW帮帮网

一、问题本质与解题思路

1.1 数独问题的核心要求

数独是一个9×9的网格，需要满足以下规则：

每行包含1-9的所有数字（不重复）
每列包含1-9的所有数字（不重复）
9个3×3的子网格（九宫格）各包含1-9的所有数字（不重复）
输入包含部分已填充数字（1-9）和待填充位置（‘.’）

1.2 回溯法的适用性分析

数独问题是典型的约束满足问题，适合用回溯法求解：

每个空白格需要尝试填充1-9的数字（选择空间）
填充需满足行、列、九宫格的唯一性约束（剪枝条件）
一旦发现无法满足约束，需要回退到上一步重新尝试（回溯操作）

二、回溯算法的核心实现

2.1 整体框架解析

public void solveSudoku(char[][] board) {
    backTracking(board); // 直接调用回溯函数求解
}

public boolean backTracking(char[][] board) {
    // 遍历整个数独网格
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            // 跳过已填充的格子
            if (board[i][j] != '.') continue;
            
            // 尝试填充1-9的数字
            for (char n = '1'; n <= '9'; n++) {
                // 检查当前数字是否合法
                if (isValid(i, j, n, board)) {
                    board[i][j] = n; // 做出选择
                    // 递归填充下一个格子，若成功则返回true
                    if (backTracking(board)) {
                        return true;
                    }
                    board[i][j] = '.'; // 回溯，撤销选择
                }
            }
            // 若1-9都无法填充，返回false表示此路径无效
            return false;
        }
    }
    // 所有格子填充完毕，返回true表示找到解
    return true;
}

2.2 合法性检查函数

public boolean isValid(int row, int col, char value, char[][] board) {
    // 检查当前行是否有重复
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == value) {
            return false;
        }
    }
    
    // 检查当前列是否有重复
    for (int j = 0; j < 9; j++) {
        if (board[j][col] == value) {
            return false;
        }
    }
    
    // 检查当前九宫格是否有重复
    int startRow = (row / 3) * 3; // 计算九宫格起始行
    int startCol = (col / 3) * 3; // 计算九宫格起始列
    for (int m = startRow; m < startRow + 3; m++) {
        for (int n = startCol; n < startCol + 3; n++) {
            if (board[m][n] == value) {
                return false;
            }
        }
    }
    
    return true; // 所有检查通过，合法
}

三、递归过程动态演示

3.1 示例输入与执行流程

以一个简化的数独示例（部分填充）为例：

5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
------+-------+------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
------+-------+------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9

3.2 关键递归步骤解析

初始调用：backTracking(board)从(0,0)开始遍历
第一个空白格：(0,2)
- 尝试填充’1’：检查发现行、列、九宫格无冲突
- 填充’1’后递归调用，继续处理下一个空白格(0,3)
冲突处理：
- 当填充某个数字导致后续格子无法合法填充时
- 触发回溯：board[i][j] = '.'，尝试下一个数字
终止条件：
- 所有格子填充完毕（i=9且j=9），返回true
- 整个递归链传递true，表示找到解

3.3 回溯树简化模型

              (0,2)
           /   |   ...   \
        '1'   '2'   ...   '9'
         /     |           \
    (0,3)   (0,3)       (0,3)
     /        |            \
成功/失败  成功/失败    成功/失败

四、算法核心技术点解析

4.1 回溯函数的布尔返回值设计

为什么返回boolean而不是void：
- 数独问题有唯一解（题目保证）
- 一旦找到解，通过return true快速终止所有递归
- 避免继续搜索其他无效路径，提升效率

4.2 九宫格索引计算的数学原理

int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;

整数除法特性：row / 3得到0-2的九宫格行索引
乘以3得到九宫格左上角的实际行索引
例如：row=4 → 4/3=1 → startRow=3（第2个九宫格的起始行）

4.3 时间复杂度分析

最坏情况：每个空白格尝试9个数字，假设共有k个空白格
时间复杂度：O(9ᵏ)，k最多为81（极端情况全空白）
实际效率：由于约束检查的剪枝作用，实际运行远快于理论值

五、优化策略与扩展思考

5.1 效率优化方向

预计算空白格位置：

提前收集所有空白格坐标，避免每次遍历整个网格

List<int[]> emptyCells = new ArrayList<>();
for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
        if (board[i][j] == '.') {
            emptyCells.add(new int[]{i, j});
        }
    }
}

优化合法性检查：

使用三个布尔数组（行、列、九宫格）记录已有数字
将检查时间从O(9)降为O(1)

boolean[][] rowUsed = new boolean[9][10];
boolean[][] colUsed = new boolean[9][10];
boolean[][] boxUsed = new boolean[9][10];

5.2 多解问题的扩展

若数独存在多个解，需修改算法收集所有解：

将返回值改为void
当找到一个解时，记录当前状态并继续回溯
移除return true的快速终止逻辑

六、常见误区与调试技巧

6.1 典型错误分析

递归终止条件错误：
- 错误：在填充完最后一个格子后未正确返回
- 解决：确保所有格子遍历完毕后返回true
回溯操作遗漏：
- 错误：填充数字后未在递归失败时恢复为’.’
- 解决：严格遵循"选择-递归-撤销"的回溯模式

6.2 调试建议

打印递归过程：

System.out.println("填充位置: (" + i + "," + j + "), 数字: " + n);

可视化数独状态：
- 在每次重要操作后打印当前数独网格
- 观察数字填充和回溯的变化过程

七、总结：回溯法解决数独问题的核心

状态表示：
- 使用9×9的字符数组直接存储数独状态
- 通过双重循环遍历每个待填充位置
选择与约束：
- 每个位置尝试1-9的数字（选择空间）
- 通过行、列、九宫格检查实现约束剪枝
递归与回溯：
- 递归处理下一个位置，成功则快速返回
- 失败则撤销当前选择，尝试下一个数字

数独问题展示了回溯法在二维空间中的典型应用，其核心在于通过有效的约束检查减少搜索空间，以及通过布尔返回值实现解的快速发现。掌握这种模式可以解决各类网格填充和约束满足问题。

LeetCode 37.解数独：回溯法在二维网格中的应用与剪枝策略