This is a solution of 36. Valid Sudoku.

Analysis

The target here is to check if a given board is a valid sudoku. The criteria are listed below,

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.

A brutal force solution would be retrieving each position on the board and checking if the element in that position has violated those three rules.

We could use 1 matrix to remember the appearance times for each number from 1 – 9 in each row. The same method can apply to column check and grid check too. So we will need 3 matrices. The grid will be indexed for 0 – 8 and mapped to the grid matrix rows. The map equation for position (i, j) would be that

$$grid\_row = (i // 3) * 3 + j // 3$$

Then we can write the code.

Code

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [[0] * 9 for _ in range(9)]
        col = [[0] * 9 for _ in range(9)]
        grid = [[0] * 9 for _ in range(9)]

        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    num = int(board[i][j]) - 1
                    grid_row = (i // 3) * 3 + j // 3
                    if row[i][num] == 1 or col[j][num] == 1 or grid[grid_row][num] == 1:
                        return False
                    row[i][num] = col[j][num] = grid[grid_row][num] = 1
        return True