Question
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits
1-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without repetition.
Note:
- A Sudoku board (partially filled) could be valid but is not necessarily solvable.
- Only the filled cells need to be validated according to the mentioned rules.
Solution (Python)
class Solution:
def checkRep(self, checklist):
#print(checklist)
for i in range(1,9+1):
count = checklist.count(str(i))
#print(i,count)
if count>1:
return False
else:
return True
def getSquare(self,i_start,j_start,board):
square_list = []
for i in range(i_start,i_start+3):
for j in range(j_start,j_start+3):
square_list.append(board[i][j])
return square_list
def isValidSudoku(self, board: List[List[str]]) -> bool:
# Check Rows
for i in range(0,9):
if self.checkRep(board[i])==False:
return False
# Check Columns
for j in range(0,9):
if self.checkRep([x[j] for x in board])==False:
return False
# Check Squares
square_coords = []
for i in range(0,3):
for j in range(0,3):
square_coords.append([i*3,j*3])
#print(square_coords)
for coord in square_coords:
square_list = self.getSquare(coord[0],coord[1],board)
if self.checkRep(square_list)==False:
return False
return True
Cracking the Coding Interview: 189 Programming Questions and Solutions