36 Valid Sudoku
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[0]) != 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 squarevariable should then becomemath.sqrt(dim)
Last modified 4yr ago