36. 有效的数独
题目描述
输入一个 9 x 9 的数独盘面 board，已填的格子是 '1' 到 '9'，空格是 '.'。盘面可以只填了一部分。
只检查已填的数字是否冲突：同一行内、同一列内、以及 9 个不重叠的 3 x 3 小宫格内，每个数字都不能出现两次或以上。
没有冲突就返回 true，否则返回 false。不需要判断盘面能否被填完，没有冲突但无解的盘面也算有效。
示例 1
输入：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
解释：所有行、列、宫格内都没有重复数字。
示例 2
输入：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
解释：与示例 1 相比只把左上角的 5 改成了 8，左上角的 3 x 3 宫格里出现了两个 8。
数据范围
board.length == 9board[i].length == 9board[i][j]是'1'到'9'中的一个数字，或者'.'。
解题思路
为 9 行、9 列、9 宫各准备一个哈希集合，共 27 个。按行逐格扫描：空格跳过；对数字 v，先算出宫号 b = (r//3)*3 + c//3，再查 v 是否已在 rows[r]、cols[c]、boxes[b] 任一集合中——在就说明重复，直接返回 false；否则把 v 同时加入这三个集合。全部扫完没有冲突就返回 true。
为什么正确
扫描到 (r,c) 之前，rows[i] / cols[j] / boxes[k] 恰好是已扫描过的格子中、第 i 行 / 第 j 列 / 第 k 宫出现过的数字集合，且其中没有重复。
复杂度分析
盘面固定 81 格，时间 O(81) = O(1)，空间 27 个集合共 O(1)。若推广到 n×n，则时间 O(n²)，空间 O(n²)。
易错点
宫号最容易算错：应是 (r//3)*3 + c//3，而不是 r//3 + c//3（会让不同宫撞号）或 r*3 + c。另外不要只检查行和列——两个相同数字可以既不同行也不同列，却位于同一宫。空格 '.' 必须跳过，不能当作字符加入集合。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
v = board[r][c]
if v == '.':
continue
b = (r // 3) * 3 + c // 3
if v in rows[r] or v in cols[c] or v in boxes[b]:
return False
rows[r].add(v)
cols[c].add(v)
boxes[b].add(v)
return Trueclass Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] rows = new boolean[9][10];
boolean[][] cols = new boolean[9][10];
boolean[][] boxes = new boolean[9][10];
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
char ch = board[r][c];
if (ch == '.') {
continue;
}
int v = ch - '0';
int b = (r / 3) * 3 + c / 3;
if (rows[r][v] || cols[c][v] || boxes[b][v]) {
return false;
}
rows[r][v] = true;
cols[c][v] = true;
boxes[b][v] = true;
}
}
return true;
}
}class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool rows[9][10] = {};
bool cols[9][10] = {};
bool boxes[9][10] = {};
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
char ch = board[r][c];
if (ch == '.') {
continue;
}
int v = ch - '0';
int b = (r / 3) * 3 + c / 3;
if (rows[r][v] || cols[c][v] || boxes[b][v]) {
return false;
}
rows[r][v] = true;
cols[c][v] = true;
boxes[b][v] = true;
}
}
return true;
}
};func isValidSudoku(board [][]byte) bool {
var rows [9][10]bool
var cols [9][10]bool
var boxes [9][10]bool
for r := 0; r < 9; r++ {
for c := 0; c < 9; c++ {
ch := board[r][c]
if ch == '.' {
continue
}
v := ch - '0'
b := (r/3)*3 + c/3
if rows[r][v] || cols[c][v] || boxes[b][v] {
return false
}
rows[r][v] = true
cols[c][v] = true
boxes[b][v] = true
}
}
return true
}var isValidSudoku = function(board) {
const rows = Array.from({ length: 9 }, () => new Set());
const cols = Array.from({ length: 9 }, () => new Set());
const boxes = Array.from({ length: 9 }, () => new Set());
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
const v = board[r][c];
if (v === '.') {
continue;
}
const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) {
return false;
}
rows[r].add(v);
cols[c].add(v);
boxes[b].add(v);
}
}
return true;
};function isValidSudoku(board: string[][]): boolean {
const rows: Set<string>[] = Array.from({ length: 9 }, () => new Set<string>());
const cols: Set<string>[] = Array.from({ length: 9 }, () => new Set<string>());
const boxes: Set<string>[] = Array.from({ length: 9 }, () => new Set<string>());
for (let r = 0; r < 9; r++) {
for (let c = 0; c < 9; c++) {
const v = board[r][c];
if (v === '.') {
continue;
}
const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) {
return false;
}
rows[r].add(v);
cols[c].add(v);
boxes[b].add(v);
}
}
return true;
}