36. 有效的数独
作者：沉默王二
发布时间：2024-06-16T12:13:20.997+0800
鲁迅曾说，人生就是在不断地挑战自己，飞得越高，可能就会跌的越痛，因为你面临的挑战越来越大。但也只有这样，才能不断修剪自己的羽毛，从而再次翱翔，重新出发。数独是数学当中一个非常有意思的项目，结合 LeetCode 来刷题也会有新的理解。
技术派阅读地址：https://paicoding.com/column/7/36
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 2 道大家完全都能掌握的题解（ 主要是理解二维数组）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。
题意
请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 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"]]
输出：true
输入：board =
[["8","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"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
### 分析 1
这道题看上去很唬人，因为输入的数据密密麻麻，尤其是对于第一次接触数独的同学来说，可能会有点懵。
但如果按照题目要求，把它拆成三个步骤来实现，就会容易得多：
第一次遍历，判断每一行是否有相同的数字
第二次遍历，判断每一列是否有相同的数字
第三次遍历，判断每一个 3 × 3 的格子里是否有相同的数字
好，我们就先按照这个思路来。
第一步，遍历二维数组，使用 HashSet 来判断是否有相同的数字，如果有，直接返回 false。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
// 检查每一行
for (int i = 0; i < 9; i++) {
Set
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c != '.') {
if (rowSet.contains(c)) {
return false; // 如果行中已经有这个数字，返回 false
}
rowSet.add(c);
}
}
}
很好理解，两个 for 循环，找到数独中的每一个数字，然后判断是否已经在 HashSet 中。
第二步，判断每一列是否有相同的数字，同样使用 HashSet 来判断。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
// 检查每一列
for (int j = 0; j < 9; j++) {
Set
for (int i = 0; i < 9; i++) {
char c = board[i][j];
if (c != '.') {
if (colSet.contains(c)) {
return false; // 如果列中已经有这个数字，返回 false
}
colSet.add(c);
}
}
}
注意这次的两个 for 循环，顺序和之前遍历行的时候不同。之前是先保持行不变，列变化，这次是先保持列不变，行变化。
第三步，我们需要把 9 × 9 的数独拆成 9 个的 3 × 3 的格子，然后判断每一个格子里是否有相同的数字。
对于每一个 3 × 3 的格子，它可以用一个二维数组来表示，比如第一个格子，它的坐标是 (0, 0)，那么它的 3 × 3 的格子就是：
(0, 0) (0, 1) (0, 2)
(1, 0) (1, 1) (1, 2)
(2, 0) (2, 1) (2, 2)
对于第二个 3 × 3 的格子，它的坐标就是在第一个的基础上往右移动 3 个单位：
(0, 3) (0, 4) (0, 5)
(1, 3) (1, 4) (1, 5)
(2, 3) (2, 4) (2, 5)
对于第五个 3 × 3 的格子，它的坐标就是在第一个的基础上往下移动 3 个单位，往右移动 3 个单位：
(3, 3) (3, 4) (3, 5)
(4, 3) (4, 4) (4, 5)
(5, 3) (5, 4) (5, 5)
以此类推，我们就需要一个步长来表示这个移动的过程。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
for (int block = 0; block < 9; block++) {
int rowStart = (block / 3) * 3;
int colStart = (block % 3) * 3;
}
然后把这个步长应用到每一个格子里，就可以得到每一个 3 × 3 的格子了。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
// 检查每一个 3x3 宫格
for (int block = 0; block < 9; block++) {
Set
int rowStart = (block / 3) * 3;
int colStart = (block % 3) * 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
char c = board[rowStart + i][colStart + j];
if (c != '.') {
if (blockSet.contains(c)) {
return false; // 如果 3x3 宫格中已经有这个数字，返回 false
}
blockSet.add(c);
}
}
}
}
好，我们来整合一下，就是这样的：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution {
public boolean isValidSudoku(char[][] board) {
// 检查每一行
for (int i = 0; i < 9; i++) {
Set
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c != '.') {
if (rowSet.contains(c)) {
return false; // 如果行中已经有这个数字，返回 false
}
rowSet.add(c);
}
}
}
// 检查每一列
for (int j = 0; j < 9; j++) {
Set
for (int i = 0; i < 9; i++) {
char c = board[i][j];
if (c != '.') {
if (colSet.contains(c)) {
return false; // 如果列中已经有这个数字，返回 false
}
colSet.add(c);
}
}
}
// 检查每一个 3x3 宫格
for (int block = 0; block < 9; block++) {
Set
int rowStart = (block / 3) * 3;
int colStart = (block % 3) * 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
char c = board[rowStart + i][colStart + j];
if (c != '.') {
if (blockSet.contains(c)) {
return false; // 如果 3x3 宫格中已经有这个数字，返回 false
}
blockSet.add(c);
}
}
}
}
return true;
}
}
来看一下题解效率：
不算高，但整个题解的过程非常清晰，容易掌握。
分析 2
在上面的题解中，我们使用了三次遍历，分别判断行、列和 3 × 3 的格子里是否有相同的数字，这样的效率就不会高。
那其实我们可以定义三个二维数组，分别表示行、列和 3 × 3 的格子里的数字，然后一次遍历就可以判断是否有相同的数字了。
不过，在此之前，我们需要明白为什么能够这样做。
对于数独，我们可以把它看成一个 9 × 9 的二维数组，那么对于每一个数字，它的坐标就是 (i, j)，其中 i 表示行，j 表示列。
对于行，我们可以用一个二维数组来表示，row[i][num] 表示第 i 行是否有数字 num，如果有，就是 true，否则就是 false。
对于列，我们也可以用一个二维数组来表示，col[j][num] 表示第 j 列是否有数字 num。
对于 3 × 3 的格子，我们同样可以用一个二维数组来表示，block[blockIndex][num] 表示第 blockIndex 个 3 × 3 的格子里是否有数字 num。
blockIndex 怎么计算呢？
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
blockIndex = (i / 3) * 3 + j / 3
i 是当前元素的行索引，j 是当前元素的列索引。
i / 3：将行索引 i 除以 3，可以得到当前元素所在的宫格行。
(i / 3) * 3：将宫格行乘以 3，可以定位到当前宫格的首个宫格索引。
j / 3：将列索引 j 除以 3，可以得到当前元素所在的宫格列。
(i / 3) * 3 + j / 3：将宫格行的首个宫格索引加上宫格列的索引，可以得到当前元素所在的宫格索引。
然后我们将数独中的字符转成索引，方便在布尔数组中记录和查找数字是否出现过，转换方法如下：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
int num = board[i][j] - '1';
比如说字符 5，它的 ASCII 码是 53，字符 1 的 ASCII 码是 49，所以 5 - 1 就是 4，这样就可以得到数字 5 的索引。
如果该数字第一次出现，就将其标记为 true。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
rows[i][num] = true;
cols[j][num] = true;
blocks[blockIndex][num] = true;
如果该数字已经出现过，就直接返回 false。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
if (rows[i][num] || cols[j][num] || blocks[blockIndex][num]) {
return false; // 如果当前数字在相应行、列或宫格中已经存在，返回 false
}
好，来看一下完整的题解：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] rows = new boolean[9][9];
boolean[][] cols = new boolean[9][9];
boolean[][] blocks = new boolean[9][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
continue;
}
int num = board[i][j] - '1';
int blockIndex = (i / 3) * 3 + j / 3;
if (rows[i][num] || cols[j][num] || blocks[blockIndex][num]) {
return false; // 如果当前数字在相应行、列或宫格中已经存在，返回 false
}
rows[i][num] = true;
cols[j][num] = true;
blocks[blockIndex][num] = true;
}
}
return true;
}
}
这次题解效率就提高了一大截，击败 99.76% 的用户。
总结
这道题目看上去很复杂，但只要我们把它拆分成三个步骤，就会变得简单起来。
尤其是判断行和列中是否出现相同的数字的前两步，非常简单。
对于第三步，稍微有点复杂，我们需要把 9 × 9 的数独拆成 9 个 3 × 3 的格子，索引的计算需要小心点。
本质上，还是考察二维数组的处理，推荐阅读：掌握 Java二维数组