36. Valid Sudoku

Post by ailswan Aug.28, 2023

36. Valid Sudoku

Array, Hash Table, Matrix  · 

Problem Statement

link: https://leetcode.com/problems/valid-sudoku/ https://leetcode.cn/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:

Input: [["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

Input: [["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

Solution Approach

Utilize hash tables and sets to validate the rules of Sudoku for rows, columns, and sub-grids; specifically, use sets to store encountered numbers in each region, ensuring that each number appears only once in its designated row, column, and 3x3 box.

Algorithm

  1. Create three separate hash tables to keep track of the digits encountered in each row, column, and 3x3 grid.
  2. Iterate over the board, for each filled cell, check its value against its corresponding row, column, and grid hash table to ensure no repetitions.
  3. If any repetition is found, return false; otherwise, continue checking the entire board and, if all checks pass, return true.

Implement

    class Solution:
      def isValidSudoku(self, board: List[List[str]]) -> bool:
          cols = defaultdict(lambda: set())
          rows = defaultdict(lambda: set())
          grids = defaultdict(lambda: set())
          for i in range(0, 9):
              for j in range(0, 9):
                  if board[i][j] == '.':
                      continue
                  if board[i][j] in cols[j]:
                      return False
                  else:
                      cols[j].add(board[i][j])
                  if board[i][j] in rows[i]:
                      return False
                  else:
                      rows[i].add(board[i][j])
                  if board[i][j] in grids[10 * (i // 3) + (j // 3)]:
                      return False
                  else:
                      grids[10 * (i // 3) + (j // 3)].add(board[i][j])
          return True