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:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
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

To validate board , we must check that each row, column, and 3x3 square contains no duplicates and contains the digits 1-9. We can do this by iterating through all the rows, columns, and squares and storing the numbers we see in a set. If we see a number that is already in the set, we return False. If we finish checking all rows, columns, and squares without finding duplicates, we return True.

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."""
    seen = set()

    for num in cells:
        if num != "." and num in seen:
            return False
        else:
            seen.add(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.

One Pass

Explanation

We can reduce the number of passes through the board by checking the row, column and 3x3 square for duplicates for each cell at the same time. We maintain a set of seen numbers for each row, column, and square. If we see a number in one of these sets, we return False. Otherwise, we add the number to the appropriate set. If we finish checking all cells without finding duplicates, we return True.

Code

from collections import defaultdict


def isValidSudoku(board: list[list[str]]) -> bool:
    """Check that ``board`` is a valid sudoku board in a single pass."""
    rows = defaultdict(set)
    columns = defaultdict(set)
    squares = defaultdict(set)

    for i in range(len(board)):
        for j in range(len(board[0])):
            cell = board[i][j]

            if cell == ".":
                continue

            if (
                cell in rows[i]
                or cell in columns[j]
                or cell in squares[(i // 3, j // 3)]
            ):
                return False

            rows[i].add(cell)
            columns[j].add(cell)
            squares[(i // 3, j // 3)].add(cell)

    return True

Test

>>> from valid_sudoku__one_pass 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__one_pass.isValidSudoku(board: list[list[str]]) → bool: Check that board is a valid sudoku board in a single pass.