37. 解数独

鲁迅说过：世界就是一个巨大的草台班子，那就让我们先从二哥的 LeetCode 刷

题笔记开始吧！

题意

编写一个程序，通过填充空格来解决数独问题。

数独的解法需遵循如下规则：

• 数字 1-9 在每一行只能出现一次。

• 数字 1-9 在每一列只能出现一次。

• 数字 1-9 在每一个以粗实线分隔的 3x3 九宫格内只能出现一次。

数独的部分空格内已填入了数字，空白格用 ‘.’ 表示。

难度

困难

示例

037.解数独-20240801155636.png

输入：board = [

["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"]]

输出：[

["5","3","4","6","7","8","9","1","2"],

["6","7","2","1","9","5","3","4","8"],

["1","9","8","3","4","2","5","6","7"],

["8","5","9","7","6","1","4","2","3"],

["4","2","6","8","5","3","7","9","1"],

["7","1","3","9","2","4","8","5","6"],

["9","6","1","5","3","7","2","8","4"],

["2","8","7","4","1","9","6","3","5"],

["3","4","5","2","8","6","1","7","9"]]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

037.解数独-20240801155716.png

分析

解数独，通常会出现在一些趣味杂志或者团建活动上，最朴素最暴力的解法就是去猜一个

数，然后判断其符不符合要求，符合就去猜下一个数。

计算机在面对这类问题的时候，因为处理速度比人脑快得多多多多，所以可以挨个枚举每

个 “坑” 应该填写的数字，然后再检验一下符不符合数独的要求，就可以得出答案了。

题目要求保证唯一解，所以我们需要记录每一个 . 的位置（也就是空白格的位置），然后

逐个枚举合法的数字，确定与当前的每一行、每一列、每个九宫格都没有冲突。

如果没有冲突，就去枚举下一个，如果有冲突的话，就表示之前猜想的数字有问题，我们

可以直接回溯到之前的状态，更换新的数字。

记住一点，就是我们回溯的时候……

必须要把状态恢复到之前的样子！

必须要把状态恢复到之前的样子！

必须要把状态恢复到之前的样子！

因为之后的操作，和上次失败的操作，在逻辑关系上是并行的。

如果没有回溯到失败之前的状态，直接向下执行，那么之前失败的状态就会对接下来的判

断造成影响，逻辑关系就有问题了。

具体的思路如下：

1. 从左到右，从上到下遍历数独板。

2. 对于每一个空格，尝试填充数字 1-9。

3. 检查填充的数字是否符合数独规则。

4. 如果填充有效，则递归处理下一个空格；如果无效，回溯（撤销填充），尝试下一个

数字。

5. 如果所有空格都填充完毕，则数独解答成功。

class Solution {

public void solveSudoku(char[][] board) {

solve(board);

}

private boolean solve(char[][] board) {

for (int i = 0; i < 9; i++) {

for (int j = 0; j < 9; j++) {

if (board[i][j] == '.') { // 发现空格

for (char c = '1'; c <= '9'; c++) { // 尝试填充数字 '1' 到 '9'

if (isValid(board, i, j, c)) { // 检查数字是否符合规则

board[i][j] = c; // 填充数字

if (solve(board)) { // 递归处理下一个空格

return true;

} else {

board[i][j] = '.'; // 回溯，撤销填充

}

}

}

return false; // 如果所有数字都不符合规则，返回 false

}

}

}

 return true; // 所有空格填充完毕，返回 true

}

private boolean isValid(char[][] board, int row, int col, char c) {

for (int i = 0; i < 9; i++) {

// 检查当前行是否有重复

if (board[row][i] == c) return false;

// 检查当前列是否有重复

if (board[i][col] == c) return false;

// 检查当前 3x3 宫格是否有重复

if (board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == c) return false;

}

return true; // 数字符合规则

}

}

其中回溯的关键步骤就这两行代码：

else {

board[i][j] = '.'; // 回溯，撤销填充

}

考虑一个简单的数独局部：

53..7....

6..195...

.98....6.

假设在位置 (0, 2) 我们尝试填入数字 4。如果后续无法找到有效的解，我们需要撤销这个

填充（即将 (0, 2) 恢复为 .），然后尝试填入其他数字。如果没有撤销步骤，位置 (0, 2)

会一直保持为 4，影响后续的尝试。

来看一下执行效率：

037.解数独-20240801162035.png

总结

本题主要就是考察回溯算法的应用，回溯算法是一种递归算法，通过不断地尝试，找到所

有的解。在这个过程中，我们需要记录每一步的状态，以便在尝试失败的时候，回溯到之

前的状态。

至于知识点，还是 Java 中的二维数组、循环遍历等。

哦，如果还有的话，就是九宫格的下标计算方法：

board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3]

我们将 9x9 数独板分为 9 个 3x3 的小宫格，每个小宫格的索引可以通过下面的方式计

算：

(0, 0), (0, 1), (0, 2) | (0, 3), (0, 4), (0, 5) | (0, 6), (0, 7), (0, 8)

(1, 0), (1, 1), (1, 2) | (1, 3), (1, 4), (1, 5) | (1, 6), (1, 7), (1, 8)

(2, 0), (2, 1), (2, 2) | (2, 3), (2, 4), (2, 5) | (2, 6), (2, 7), (2, 8)

-----------------------+-------------------------+-------------------------

(3, 0), (3, 1), (3, 2) | (3, 3), (3, 4), (3, 5) | (3, 6), (3, 7), (3, 8)

(4, 0), (4, 1), (4, 2) | (4, 3), (4, 4), (4, 5) | (4, 6), (4, 7), (4, 8)

(5, 0), (5, 1), (5, 2) | (5, 3), (5, 4), (5, 5) | (5, 6), (5, 7), (5, 8)

-----------------------+-------------------------+-------------------------

(6, 0), (6, 1), (6, 2) | (6, 3), (6, 4), (6, 5) | (6, 6), (6, 7), (6, 8)

(7, 0), (7, 1), (7, 2) | (7, 3), (7, 4), (7, 5) | (7, 6), (7, 7), (7, 8)

(8, 0), (8, 1), (8, 2) | (8, 3), (8, 4), (8, 5) | (8, 6), (8, 7), (8, 8)

• 对于给定的行索引 row 和列索引 col，我们可以通过 row / 3 和 col / 3 分别确定它们

所在的 3x3 宫格。

• row / 3 * 3 得到 3x3 宫格的行起点。

• col / 3 * 3 得到 3x3 宫格的列起点。

• 再使用一个辅助变量 i，其取值范围为 0 到 8，用于遍历 3x3 宫格中的所有位置。

• i / 3 和 i % 3：分别计算 3x3 宫格内部的行和列偏移量。

假设我们正在检查元素 (4, 5) 是否符合数独规则：

• row = 4，col = 5

• row / 3 * 3 = 1 * 3 = 3：起始行索引是 3

• col / 3 * 3 = 1 * 3 = 3：起始列索引是 3`

通过遍历 i 从 0 到 8，可以得到 3x3 宫格中的所有元素位置：

• 当 i = 0：(3 + 0 / 3, 3 + 0 % 3) = (3, 3)

• 当 i = 1：(3 + 1 / 3, 3 + 1 % 3) = (3, 4)

• 当 i = 2：(3 + 2 / 3, 3 + 2 % 3) = (3, 5)

• …

• 当 i = 8：(3 + 8 / 3, 3 + 8 % 3) = (5, 5)

这样，我们就可以遍历当前元素所在的整个 3x3 宫格，并检查是否有重复的数字。

力扣链接：https://leetcode.cn/problems/sudoku-solver/