36. 有效的数独

鲁迅曾说，人生就是在不断地挑战自己，飞得越高，可能就会跌的越痛，因为你

面临的挑战越来越大。但也只有这样，才能不断修剪自己的羽毛，从而再次翱

翔，重新出发。数独是数学当中一个非常有意思的项目，结合 LeetCode 来刷题

也会有新的理解。

题意

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有

效即可。

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

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

• 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。

• 只需要根据以上规则，验证已经填入的数字是否有效即可。

• 空白格用 ‘.’ 表示。

036.%E6%9C%89%E6%95%88%E7%9A%84%E6%95%B0%E7%8B%AC-20240616072421.

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

输出：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。

// 检查每一行

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

Set<Character> rowSet = new HashSet<>();

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 来判断。

// 检查每一列

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

Set<Character> colSet = new HashSet<>();

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 的格子，然后判断每一个格子里是否

有相同的数字。

036.%E6%9C%89%E6%95%88%E7%9A%84%E6%95%B0%E7%8B%AC-20240616075509.

png

对于每一个 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)

以此类推，我们就需要一个步长来表示这个移动的过程。

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

int rowStart = (block / 3) * 3;

int colStart = (block % 3) * 3;

}

然后把这个步长应用到每一个格子里，就可以得到每一个 3 × 3 的格子了。

// 检查每一个 3x3 宫格

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

Set<Character> blockSet = new HashSet<>();

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);

}

}

}

}

好，我们来整合一下，就是这样的：

class Solution {

public boolean isValidSudoku(char[][] board) {

// 检查每一行

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

Set<Character> rowSet = new HashSet<>();

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<Character> colSet = new HashSet<>();

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<Character> blockSet = new HashSet<>();

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;

}

}

来看一下题解效率：

036.%E6%9C%89%E6%95%88%E7%9A%84%E6%95%B0%E7%8B%AC-20240616080722.

png

不算高，但整个题解的过程非常清晰，容易掌握。

分析 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 怎么计算呢？

blockIndex = (i / 3) * 3 + j / 3

i 是当前元素的行索引，j 是当前元素的列索引。

036.%E6%9C%89%E6%95%88%E7%9A%84%E6%95%B0%E7%8B%AC-20240616115659.

png

• i / 3：将行索引 i 除以 3，可以得到当前元素所在的宫格行。

• (i / 3) * 3：将宫格行乘以 3，可以定位到当前宫格的首个宫格索引。

• j / 3：将列索引 j 除以 3，可以得到当前元素所在的宫格列。

• (i / 3) * 3 + j / 3：将宫格行的首个宫格索引加上宫格列的索引，可以得到当前元素

所在的宫格索引。

然后我们将数独中的字符转成索引，方便在布尔数组中记录和查找数字是否出现过，转换

方法如下：

int num = board[i][j] - '1';

比如说字符 5，它的 ASCII 码是 53，字符 1 的 ASCII 码是 49，所以 5 - 1 就是 4，这样就

可以得到数字 5 的索引。

如果该数字第一次出现，就将其标记为 true。

rows[i][num] = true;

cols[j][num] = true;

blocks[blockIndex][num] = true;

如果该数字已经出现过，就直接返回 false。

if (rows[i][num] || cols[j][num] || blocks[blockIndex][num]) {

return false; // 如果当前数字在相应行、列或宫格中已经存在，返回 false

}

好，来看一下完整的题解：

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% 的用户。

036.%E6%9C%89%E6%95%88%E7%9A%84%E6%95%B0%E7%8B%AC-20240616120409.

png

总结

这道题目看上去很复杂，但只要我们把它拆分成三个步骤，就会变得简单起来。

尤其是判断行和列中是否出现相同的数字的前两步，非常简单。

对于第三步，稍微有点复杂，我们需要把 9 × 9 的数独拆成 9 个 3 × 3 的格子，索引的计

算需要小心点。

本质上，还是考察二维数组的处理，推荐阅读：掌握 Java 二维数组

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