Question: https://leetcode.com/problems/valid-sudoku/description/
I divided there problem in 3 parts:
checking rows and columns would be done by this method:
# same logic would be used to see if row/column is valid or not.
def isValidRC(self, row_col: List[str]) -> bool:
temp = set()
for i in row_col:
if i != '.':
if i in temp:
return False
temp.add(i)
return True
For fetching rows:
# check all the rows
for row in board:
if not self.isValidRC(row):
return False
For fetching columns:
# check all the columns
for i in range(9):
col = [row[i] for row in board]
if not self.isValidRC(col):
return False
For checking 3x3 grids I created 2 methods:
def isValid3x3(self, sub):
temp = set()
for row in sub:
for ele in row:
if ele != '.':
if ele in temp:
return False
temp.add(ele)
return True
def get3x3(self,board,*n):
sub = []
for rno in range(n[0],n[1]):
row = board[rno][n[2]:n[3]]
sub.append(row)
if not self.isValid3x3(sub):
return False
return True
I checked all the 3x3 like this:
# check all the 3x3 sub boards
# first 3x3
if not self.get3x3(board,0,3,0,3):
return False
# second 3x3
if not self.get3x3(board,0,3,3,6):
return False
# third 3x3
if not self.get3x3(board,0,3,6,9):
return False
# fourth 3x3
if not self.get3x3(board,3,6,0,3):
return False
# fifth 3x3
if not self.get3x3(board,3,6,3,6):
return False
# sixth 3x3
if not self.get3x3(board,3,6,6,9):
return False
# seventh 3x3
if not self.get3x3(board,6,9,0,3):
return False
# eighth 3x3
if not self.get3x3(board,6,9,3,6):
return False
# ninth 3x3
if not self.get3x3(board,6,9,6,9):
return False
I know this is a brute-force solution. But I have already spent more than 4 hours today. And I have a lot of other tasks to complete.
Final solution:
class Solution:
# same logic would be used to see if row/column is valid or not.
def isValidRC(self, row_col):
temp = set()
for i in row_col:
if i != '.':
if i in temp:
return False
temp.add(i)
return True
def isValid3x3(self, sub):
temp = set()
for row in sub:
for ele in row:
if ele != '.':
if ele in temp:
return False
temp.add(ele)
return True
def get3x3(self,board,*n):
sub = []
for rno in range(n[0],n[1]):
row = board[rno][n[2]:n[3]]
sub.append(row)
if not self.isValid3x3(sub):
return False
return True
def isValidSudoku(self, board: List[List[str]]) -> bool:
# check all the rows
for row in board:
if not self.isValidRC(row):
return False
# check all the columns
for i in range(9):
col = [row[i] for row in board]
if not self.isValidRC(col):
return False
# check all the 3x3 sub boards
# first 3x3
if not self.get3x3(board,0,3,0,3):
return False
# second 3x3
if not self.get3x3(board,0,3,3,6):
return False
# third 3x3
if not self.get3x3(board,0,3,6,9):
return False
# fourth 3x3
if not self.get3x3(board,3,6,0,3):
return False
# fifth 3x3
if not self.get3x3(board,3,6,3,6):
return False
# sixth 3x3
if not self.get3x3(board,3,6,6,9):
return False
# seventh 3x3
if not self.get3x3(board,6,9,0,3):
return False
# eighth 3x3
if not self.get3x3(board,6,9,3,6):
return False
# ninth 3x3
if not self.get3x3(board,6,9,6,9):
return False
return True