36. 有效的数独
36. 有效的数独
题目
Determine if a 9 x 9
Sudoku board is valid. Only the filled cells need to be validated according to the following rules :
- Each row must contain the digits
1-9
without repetition. - Each column must contain the digits
1-9
without repetition. - Each of the nine
3 x 3
sub-boxes of the grid must contain the digits1-9
without repetition.
Note:
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
Example 1:
Input: 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"]]
Output: true
Example 2:
Input: 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"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
Constraints:
board.length == 9
board[i].length == 9
board[i][j]
is a digit1-9
or'.'
.
题目大意
判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
解题思路
- 给出一个数独的棋盘,要求判断这个棋盘当前是否满足数独的要求:即行列是否都只包含 1-9,每个九宫格里面是否也只包含 1-9 。
- 注意这题和 第 37 题 是不同的,这一题是判断当前棋盘状态是否满足数独的要求,而 第 37 题 是要求求解数独。本题中的棋盘有些是无解的,但是棋盘状态是满足题意的。
- 只需要遍历矩阵,分别判断行列和九宫格内有没有重复的数字即可;
- 矩阵的数组下标 (
i_j
) 如下,难点在于如何计算九宫格内元素的下标:box[i][j] = board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)]
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
代码
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function (board) {
for (let i = 0; i < 9; i++) {
let row = new Set();
let col = new Set();
let box = new Set();
for (let j = 0; j < 9; j++) {
let _row = board[i][j];
let _col = board[j][i];
let _box =
board[3 * Math.floor(i / 3) + Math.floor(j / 3)][3 * (i % 3) + (j % 3)];
if (_row != '.') {
if (row.has(_row)) return false;
row.add(_row);
}
if (_col != '.') {
if (col.has(_col)) return false;
col.add(_col);
}
if (_box != '.') {
if (box.has(_box)) return false;
box.add(_box);
}
}
}
return true;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
37 | 解数独 | [✓] | 数组 哈希表 回溯 1+ | |
2133 | 检查是否每一行每一列都包含全部整数 | 数组 哈希表 矩阵 |