Valid Sudoku

Problem

https://leetcode.com/problems/valid-sudoku/

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 '.'.

Pattern

Array, Hash Table, Matrix

Approaches

Hash Sets

Explanation

Check that each row, column, and 3x3 square contains no duplicates and contains the digits 1-9. Return False if these conditions don’t hold.

Code

def isValidSudoku(board: list[list[str]]) -> bool:
    """Check that ``board`` is a valid sudoku board."""
    for i in range(9):
        row = board[i]
        if not is_valid(row):
            return False

    for j in range(9):
        col = [board[i][j] for i in range(9)]
        if not is_valid(col):
            return False

    for x in range(0, 9, 3):
        for y in range(0, 9, 3):
            square = [board[x + i][y + j] for i in range(3) for j in range(3)]
            if not is_valid(square):
                return False

    return True


def is_valid(cells: list[str]) -> bool:
    """Check that ``cells`` has no duplicates and contains the digits 1-9."""
    nums = [cell for cell in cells if cell != "."]
    one_through_nine = {str(i) for i in range(1, 10)}

    if len(set(nums)) < len(nums):
        return False

    for num in nums:
        if num not in one_through_nine:
            return False
        else:
            one_through_nine.remove(num)

    return True

Test

>>> from valid_sudoku__hash_sets import isValidSudoku
>>> 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'],
... ]
>>> isValidSudoku(board)
True
>>> 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'],
... ]
>>> isValidSudoku(board)
False

Complexity

\(n\) is the size of a block (3 for a 9x9 board)

Measure	Complexity	Notes
Time	\(O(n^4)\)	number of rows, columns, and squares to check is \(3n^2\) and there are \(n^2\) cells in each row, column, and square
Auxiliary Space	\(O(n^2)\)	numbers in each row, column, and square are stored in a set for checking duplicates and valid digits

valid_sudoku__hash_sets.isValidSudoku(board: list[list[str]]) → bool

Check that board is a valid sudoku board.

valid_sudoku__hash_sets.is_valid(cells: list[str]) → bool

Check that cells has no duplicates and contains the digits 1-9.