LeetCode Top Interview 150

36. Valid Sudoku

Medium

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:

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

Example 2:

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

Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8’s in the top left 3x3 sub-box, it is invalid.

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.

Solution

from typing import List

class Solution:
    def __init__(self):
        self.j1 = 0
        self.i1 = [0] * 9
        self.b1 = [0] * 9

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for i in range(9):
            for j in range(9):
                res = self._checkValid(board, i, j)
                if not res:
                    return False
        return True

    def _checkValid(self, board: List[List[str]], i: int, j: int) -> bool:
        if j == 0:
            self.j1 = 0
        if board[i][j] == '.':
            return True
        val = int(board[i][j])
        if self.j1 == (self.j1 | (1 << (val - 1))):
            return False
        self.j1 |= 1 << (val - 1)
        if self.i1[j] == (self.i1[j] | (1 << (val - 1))):
            return False
        self.i1[j] |= 1 << (val - 1)
        b = (i // 3) * 3 + j // 3
        if self.b1[b] == (self.b1[b] | (1 << (val - 1))):
            return False
        self.b1[b] |= 1 << (val - 1)
        return True

This site is open source. Improve this page.