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)