# 36 Valid Sudoku

Determine if a Sudoku is valid, according to:Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character`'.'`. A partially filled sudoku which is valid.
Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated. (A completely empty board is a valid square).
The Idea: A board is valid if all the rows, columns, and squares contain no duplicate integers.
Complexity: O(n^2) time and O(n) space with n is the len(sqrt(board))
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
dim = len(board)
if not board or dim == 0 or \
len(board) != dim:
return False
# rule 1: no duplicates in rows
for row in board:
row_elms = [elm for elm in row if elm != '.']
if len(set(row_elms)) != len(row_elms):
return False
# rule 2: no duplicates in cols
for i in range(dim):
col_elms = [board[j][i] for j in range(dim) if board[j][i] != '.']
if len(set(col_elms)) != len(col_elms):
return False
# rule 3: no duplicates in each square grid
square = int(dim/3)
for row_mult in range(square):
for col_mult in range(square):
square_elm = []
for i in range(row_mult*square, (row_mult*square) + square):
for j in range(col_mult*square, (col_mult*square) + square):
if board[i][j] != '.':
square_elm.append(board[i][j])
if len(set(square_elm)) != len(square_elm):
return False
return True
Discussion
• If the board is not necessarily 9x9, and if we wanted to generalize this algorithm. Here are some of the changes that need to be made.
• The board must be a perfect square. e.g. `0^2, 1^1, 2^2 ... , n^n`
• `square`variable should then become `math.sqrt(dim)`