Valid Sudoku
You are given a a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:
Each row must contain the digits 1-9 without duplicates.
Each column must contain the digits 1-9 without duplicates.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates.
Return true if the Sudoku board is valid, otherwise return false
Note: A board does not need to be full or be solvable to be valid.
Example 1:
Input: board =
[["1","2",".",".","3",".",".",".","."],
["4",".",".","5",".",".",".",".","."],
[".","9","8",".",".",".",".",".","3"],
["5",".",".",".","6",".",".",".","4"],
[".",".",".","8",".","3",".",".","5"],
["7",".",".",".","2",".",".",".","6"],
[".",".",".",".",".",".","2",".","."],
[".",".",".","4","1","9",".",".","8"],
[".",".",".",".","8",".",".","7","9"]]
Output: true
Example 2:
Input: board =
[["1","2",".",".","3",".",".",".","."],
["4",".",".","5",".",".",".",".","."],
[".","9","1",".",".",".",".",".","3"],
["5",".",".",".","6",".",".",".","4"],
[".",".",".","8",".","3",".",".","5"],
["7",".",".",".","2",".",".",".","6"],
[".",".",".",".",".",".","2",".","."],
[".",".",".","4","1","9",".",".","8"],
[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: There are two 1’s in the top-left 3x3 sub-box.
Constraints:
board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or ‘.’.
Solution
As there the constraints says, board[i][j] can only be a digit 1-9 or '.', and a board does not need to be full or be solvable to be valid, greatly simplifying the problem.
All we need to do is to extract all numbers from every row, col and sub-board, putting them into a dictionary and checking if the value in dictionary is greater than 1.
Code
I guess this problem is trying to evaluate my sliding skills?
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
def checkValid(nums: List[str]) -> bool:
num_dict = {}
for num in nums:
if num == ".":
continue
num = int(num)
num_dict[num] = num_dict.get(num, 0) + 1
for value in num_dict.values():
if value > 1:
return False
return True
for row in board:
if not checkValid(row):
return False
cols_board = [[board[i][j] for i in range(9)] for j in range(9)]
for col in cols_board:
if not checkValid(col):
return False
for i in range(0, 9, 3):
for j in range(0, 9, 3):
sub_board = board[i][j:j+3] + board[i+1][j:j+3] + board[i+2][j:j+3]
if not checkValid(sub_board):
return False
return True
