The problem
A 9 × 9 Sudoku board is partly filled with digits 1–9; empty cells are .. Decide whether the filled cells break any rule: no digit may repeat in a row, in a column, or in any of the nine 3 × 3 boxes.
The board does not need to be solvable — only the cells already filled are checked.
Examples
- 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
- 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
Constraints
boardis 9 × 9.- Each cell is a digit 1–9 or
..
The idea
Every filled cell belongs to exactly one row, one column and one box. Keep, for each of the 27 units, a record of which digits it already holds; the box of cell (r, c) is number (r ÷ 3) × 3 + c ÷ 3, rounding down.
Scan the board once. For each digit, if its row, column or box has already seen it, the board is invalid; otherwise record it in all three. A record of nine digits fits in nine bits of one integer, so each check is a single AND.
- Time
- O(1) — always 81 cells (O(n²) for an n × n board)
- Space
- O(1) — 27 small records
Solution · every language run against every case
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)] # box index: (r // 3) * 3 + c // 3 for r in range(9): for c in range(9): d = board[r][c] if d == '.': continue b = (r // 3) * 3 + c // 3 if d in rows[r] or d in cols[c] or d in boxes[b]: return False rows[r].add(d) cols[c].add(d) boxes[b].add(d) return True