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-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without 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.
Example 1:
Input: board = [[“5”,“3”,".",".",“7”,".",".",".","."] ,[“6”,".",".",“1”,“9”,“5”,".",".","."] ,[".",“9”,“8”,".",".",".",".",“6”,"."] ,[“8”,".",".",".",“6”,".",".",".",“3”] ,[“4”,".",".",“8”,".",“3”,".",".",“1”] ,[“7”,".",".",".",“2”,".",".",".",“6”] ,[".",“6”,".",".",".",".",“2”,“8”,"."] ,[".",".",".",“4”,“1”,“9”,".",".",“5”] ,[".",".",".",".",“8”,".",".",“7”,“9”]] Output: true
Example 2:
Input: board = [[“8”,“3”,".",".",“7”,".",".",".","."] ,[“6”,".",".",“1”,“9”,“5”,".",".","."] ,[".",“9”,“8”,".",".",".",".",“6”,"."] ,[“8”,".",".",".",“6”,".",".",".",“3”] ,[“4”,".",".",“8”,".",“3”,".",".",“1”] ,[“7”,".",".",".",“2”,".",".",".",“6”] ,[".",“6”,".",".",".",".",“2”,“8”,"."] ,[".",".",".",“4”,“1”,“9”,".",".",“5”] ,[".",".",".",".",“8”,".",".",“7”,“9”]] Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8’s in the top left 3x3 sub-box, it is invalid.
Constraints:
board.length == 9
board[i].length == 9
board[i][j] is a digit 1-9 or '.'.
- code
class Solution {
public char[] buildMatrix(int x, int y, char[][] board){
char[] matrix = new char[9];
int count = 0;
for (int i = x; i < x + 3; i++){
for (int j = y; j < y + 3; j++){
matrix[count++] = board[i][j];
}
}
return matrix;
}
public boolean checkDuplicate(char[] chars){
Set s = new HashSet();
for(Character c: chars){
if (c != '.'){
if (s.contains(c)) return false;
s.add(c);
}
}
return true;
}
public boolean isValidSudoku(char[][] board) {
for (int i = 0; i <= 6; i += 3){
for(int j = 0; j <= 6; j += 3){
if (!checkDuplicate(buildMatrix(i, j, board))) return false;
}
}
for (char[] row: board){
if (!checkDuplicate(row)) return false;
}
for (int j = 0; j < 9; j++){
char[] col = new char[9];
for (int i = 0; i < 9; i++){
col[i] = board[i][j];
}
if (!checkDuplicate(col)) return false;
}
return true;
}
}
- code
class Solution:
def isValidSudoku(self, board):
return all([
self.isRowValid(board),
self.isColValid(board),
self.isSubBoxValid(board)
])
def isNineNoDuplicate(self, nums):
cleanNum = list(filter(lambda x: x!='.', nums))
return len(set(cleanNum)) == len(cleanNum)
def isRowValid(self, board):
return all([self.isNineNoDuplicate(row) for row in board])
def isColValid(self, board):
return all([self.isNineNoDuplicate(col) for col in zip(*board)])
def isSubBoxValid(self, board):
subBoxDict = collections.defaultdict(list)
for row in range(9):
for col in range(9):
if board[row][col] != '.':
key = (row // 3) * 3 + col // 3
if board[row][col] in subBoxDict[key]:
return False
subBoxDict[key].append(board[row][col])
return True
- code
class Solution:
def isValidSudoku(self, board):
return (self.is_row_valid(board) and
self.is_col_valid(board) and
self.is_square_valid(board))
def is_row_valid(self, board):
for row in board:
if not self.is_unit_valid(row):
return False
return True
def is_col_valid(self, board):
for col in zip(*board):
if not self.is_unit_valid(col):
return False
return True
def is_square_valid(self, board):
for i in (0, 3, 6):
for j in (0, 3, 6):
square = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]
if not self.is_unit_valid(square):
return False
return True
def is_unit_valid(self, unit):
unit = [i for i in unit if i != '.']
return len(set(unit)) == len(unit)
code twist the ans from EPI
def isValidSudoku(self, board: List[List[str]]) -> bool:
# Return True if subarray
# board[start_row:end_row][start_col:end_col] contains any
# duplicates in {1, 2, ..., len(board)}; otherwise return
# False.
def has_duplicate(block):
block = list(filter(lambda x: x != '.', block))
return len(block) != len(set(block))
n = len(board)
# Check row and column constraints.
if any(
has_duplicate([board[i][j] for j in range(n)])
or has_duplicate([board[j][i] for j in range(n)])
for i in range(n)):
return False
# Check region constraints.
region_size = int(math.sqrt(n))
return all(not has_duplicate([
board[a][b]
for a in range(region_size * I, region_size * (I + 1))
for b in range(region_size * J, region_size * (J + 1))
]) for I in range(region_size) for J in range(region_size))
code own
def isValidSudoku(self, board: List[List[str]]) -> bool:
def check9num(nums):
seen = []
for v in nums:
if v != '.' :
if v not in seen:
seen.append(v)
else:
return False
return True
if not all(list(check9num(row) for row in board)):
return False
for i in range(9):
thiscol = []
for j in range(9):
thiscol.append(board[j][i])
if not check9num(thiscol):
return False
for I in range(3):
for J in range(3):
little_squire = []
for i in range(3*I, 3*(I+1)):
for j in range(3*J, 3*(J+1)):
little_squire.append(board[i][j])
if not check9num(little_squire):
return False
return True