Valid Soduku
Last updated
Was this helpful?
Last updated
Was this helpful?
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 '.'.
Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
if not board:
return False
inspectH = {}
rows = len(board)
cols = len(board[0])
if rows != 9 or cols != 9:
return False
for i in xrange(rows):
row_name = "row_" + str(i)
#print row_name
for j in xrange(cols):
item = board[i][j]
if item == '.':
continue
***# 1. keep collecting the items respective to each column***
col_name = "col_" + str(j)
if col_name not in inspectH:
inspectH[col_name] = [item]
else:
inspectH[col_name].append(item)
***# 2. keep collecting the items respective to each row***
if row_name not in inspectH:
inspectH[row_name] = [item]
else:
inspectH[row_name].append(item)
***# 3. keep collecting the items with respect to each basket
# this will help inspect each internal 3x3 soduku grids
# after every 3 rows***
if j <= 2:
basket_name = "basket_1"
elif j <= 5:
basket_name = "basket_2"
else:
basket_name = "basket_3"
if basket_name not in inspectH:
inspectH[basket_name] = [item]
else:
inspectH[basket_name].append(item)
***# now check the duplicates for every row***
if row_name in inspectH:
if len(inspectH[row_name]) != len(set(inspectH[row_name])):
return False
else:
del inspectH[row_name]
***# now check the duplicates for the baskets - for every 3 rows***
if (i+1) % 3 == 0:
if "basket_1" in inspectH:
if len(inspectH["basket_1"]) != len(set(inspectH["basket_1"])):
return False
else:
del inspectH["basket_1"]
if "basket_2" in inspectH:
if len(inspectH["basket_2"]) != len(set(inspectH["basket_2"])):
return False
else:
del inspectH["basket_2"]
if "basket_3" in inspectH:
if len(inspectH["basket_3"]) != len(set(inspectH["basket_3"])):
return False
else:
del inspectH["basket_3"]
***# outside the for loops check the duplicates for each colum***
for k, v in inspectH.iteritems():
if len(v) != len(set(v)):
return False
***# finally all is well. so return True***
return True