Friedrich Ewald My Personal Website

Leetcode: Valid sudoku

Given a Sudoku field as a two-dimension list, determine if the field is valid. A valid field only has the number 1-9 once in each sub-field, each row, and each column. The field is not completely filled and we don’t need to check for a valid solution. The solution for this task is written in the conditions for a valid Sudoku field. We create a set for each row, each column, and each sub-field. If a number is duplicated in any of those, the field is not valid. If we don’t find any violation until the end, the field is valid. The remaining problem is to filter out the empty fields (.) and to find the correct sub-field. For the second part, we can leverage Pythons full integer division and determine the field as follows: field = 3 * (row // 3) + (column // 3). This yields numbers from [0-8]. This solution is faster than 96% of the submitted solutions at leetcode. It does use O(3*n) memory in the worst case, as every element needs to be stored in each set. 

from typing import List

class Solution:
  def isValidSudoku(self, board: List[List[str]]) -> bool:
    rows = [set() for _ in board]
    cols = [set() for _ in board]
    subfields = [set() for _ in range(9)]
    for i in range(len(board)):
      for j in range(len(board[0])):
        if board[i][j] == '.':
          continue
        
        if board[i][j] in rows[i]:
          return False
        rows[i].add(board[i][j])
        if board[i][j] in cols[j]:
          return False
        cols[j].add(board[i][j])

        field = 3 * (i // 3) + (j // 3)
        if board[i][j] in subfields[field]:
          return False
        subfields[field].add(board[i][j])
    return True


if __name__ == '__main__':
  s = Solution()

  # Valid board
  board1 = [["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"]]
  
  # Invalid board
  board2 = [["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"]]

  print(s.isValidSudoku(board1), True)
  print(s.isValidSudoku(board2), False)

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.

Related Posts