037.解数独
作者：沉默王二
发布时间：2024-08-01T16:48:43.064+0800
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 1 道大家完全都能掌握的题解（ 主要是理解二维数组）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
技术派阅读地址：https://paicoding.com/column/7/37
鲁迅说过：世界就是一个巨大的草台班子，那就让我们先从二哥的 LeetCode 刷题笔记开始吧！
题意
编写一个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 九宫格内只能出现一次。
数独的部分空格内已填入了数字，空白格用 '.' 表示。
难度
困难
示例
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：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"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
分析
解数独，通常会出现在一些趣味杂志或者团建活动上，最朴素最暴力的解法就是去猜一个数，然后判断其符不符合要求，符合就去猜下一个数。
计算机在面对这类问题的时候，因为处理速度比人脑快得多多多多，所以可以挨个枚举每个 “坑” 应该填写的数字，然后再检验一下符不符合数独的要求，就可以得出答案了。
题目要求保证唯一解，所以我们需要记录每一个 . 的位置（也就是空白格的位置），然后逐个枚举合法的数字，确定与当前的每一行、每一列、每个九宫格都没有冲突。
如果没有冲突，就去枚举下一个，如果有冲突的话，就表示之前猜想的数字有问题，我们可以直接回溯到之前的状态，更换新的数字。
记住一点，就是我们回溯的时候……
必须要把状态恢复到之前的样子！
必须要把状态恢复到之前的样子！
必须要把状态恢复到之前的样子！
因为之后的操作，和上次失败的操作，在逻辑关系上是并行的。
如果没有回溯到失败之前的状态，直接向下执行，那么之前失败的状态就会对接下来的判断造成影响，逻辑关系就有问题了。
具体的思路如下：
从左到右，从上到下遍历数独板。
对于每一个空格，尝试填充数字 1-9。
检查填充的数字是否符合数独规则。
如果填充有效，则递归处理下一个空格；如果无效，回溯（撤销填充），尝试下一个数字。
如果所有空格都填充完毕，则数独解答成功。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
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; // 数字符合规则
}
}
其中回溯的关键步骤就这两行代码：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
else {
board[i][j] = '.'; // 回溯，撤销填充
}
考虑一个简单的数独局部：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
5 3 . . 7 . . . .
6 . . 1 9 5 . . .
. 9 8 . . . . 6 .
假设在位置 (0, 2) 我们尝试填入数字 4。如果后续无法找到有效的解，我们需要撤销这个填充（即将 (0, 2) 恢复为 .），然后尝试填入其他数字。如果没有撤销步骤，位置 (0, 2) 会一直保持为 4，影响后续的尝试。
来看一下执行效率：
总结
本题主要就是考察回溯算法的应用，回溯算法是一种递归算法，通过不断地尝试，找到所有的解。在这个过程中，我们需要记录每一步的状态，以便在尝试失败的时候，回溯到之前的状态。
哦，如果还有的话，就是九宫格的下标计算方法：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3]
我们将 9x9 数独板分为 9 个 3x3 的小宫格，每个小宫格的索引可以通过下面的方式计算：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
(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/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 5800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！