Valid Sudoku
MediumArrays & Hashing
You are given a 9 x 9 Sudoku board as a list of 9 rows, each a list of 9 single-character strings. A cell holds a digit "1" to "9", or "." if it is empty.
Return True if the filled cells break none of these rules, and False otherwise:
- No digit appears twice in the same row.
- No digit appears twice in the same column.
- No digit appears twice in the same 3 x 3 box. The board is split into nine non-overlapping boxes: rows 0-2, 3-5 and 6-8 crossed with columns 0-2, 3-5 and 6-8.
Empty cells are ignored. You only check the cells that are already filled; the board does not need to be solvable or complete.
Example 1
- Input:
- board = [[".","3","6",".","1",".",".",".","."],["3",".",".","2",".",".",".",".","."],["1",".",".",".",".",".","2","7","."],[".",".","4","7",".","2",".",".","5"],[".",".",".","1","9",".","3",".","4"],[".",".",".","3","6",".","7",".","2"],["4","9","1",".",".","3",".",".","."],[".",".","7",".",".",".","6",".","."],[".","6","3","8",".",".",".","4","1"]]
- Output:
- False
- Explanation
- The "3" at row 0, column 1 and the "3" at row 1, column 0 are in different rows and different columns, but they sit in the same 3 x 3 box, which is not allowed. (Rows and columns are numbered from 0.)
Example 2
- Input:
- board = [[".",".","6",".","1",".",".",".","."],["3",".",".","2",".",".",".",".","."],["1",".",".",".",".",".","2","7","."],[".",".","4","7",".","2",".",".","5"],[".",".",".","1","9",".","3",".","4"],[".",".",".","3","6",".","7",".","2"],["4","9","1",".",".","3",".",".","."],[".",".","7",".",".",".","6",".","."],[".","6","3","8",".",".",".","4","1"]]
- Output:
- True
- Explanation
- Every filled digit is unique within its row, its column and its 3 x 3 box. The many empty cells do not matter.
Example 3
- Input:
- board = [["4",".","6",".","1",".",".",".","."],["3",".",".","2",".",".",".",".","."],["1",".",".",".",".",".","2","7","."],[".",".","4","7",".","2",".",".","5"],[".",".",".","1","9",".","3",".","4"],[".",".",".","3","6",".","7",".","2"],["4","9","1",".",".","3",".",".","."],[".",".","7",".",".",".","6",".","."],[".","6","3","8",".",".",".","4","1"]]
- Output:
- False
- Explanation
- Column 0 holds "4" in both row 0 and row 6. Those two cells are in different boxes and neither row repeats a digit, but the column rule is broken.
Constraints
board.length == 9board[i].length == 9board[i][j]is a digit"1"-"9"or"."