Problem description:

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-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:

https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png

1
2
3
4
5
6
7
8
9
10
11
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

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        def row_valid(board):
            for row in board:
                if not valid(row):
                    return False
            return True
        def col_valid(board):
            for col in zip(*board):
                if not valid(col):
                    return False
            return True
        def box_valid(board):
            for i in (0, 3, 6):
                for j in (0, 3, 6):
                    square = [board[x][y] for x in range(i, i+3) for y in range(j, j+3)]
                    if not valid(square):
                        return False
            return True
                    
        def valid(unit):
            unit = [i for i in unit if i != '.']
            return len(unit) == len(set(unit))
        
        return row_valid(board) and col_valid(board) and box_valid(board)

time complexity: $O()$
space complexity: $O()$
reference:
related problem: