# 36. Valid Sudoku
Determine if a 9x9 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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
A partially filled sudoku which is valid.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
Example 1:
Input:
[
["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:
[
["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.
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.
- The given board contain only digits 1-9 and the character '.'.
- The given board size is always 9x9.
# Solution
Approach 1: Verify each row, column, and sub-box.
# Code (Python)
Approach 1:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# idea: number the rows, cols, boxes from 1-9. Go through each number on the board, mark its presence.
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for i in range(9):
for j in range(9):
if board[i][j] == '.':
continue
if (board[i][j] in rows[i]) or (board[i][j] in cols[j]) or (board[i][j] in boxes[(i//3) * 3 + j//3]):
return False
rows[i].add(board[i][j])
cols[j].add(board[i][j])
boxes[(i//3) * 3 + j//3].add(board[i][j])
return True
#######################
def isValidSudoku(self, board: List[List[str]]) -> bool:
for row in board:
if not self._verify((num for num in row)):
return False
for col in range(len(board[0])):
if not self._verify((board[i][col] for i in range(len(board)))):
return False
offsets = ((0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2))
for i in range(3):
for j in range(3):
if not self._verify((board[3*i+offset[0]][3*j+offset[1]] for offset in offsets)):
return False
return True
def _verify(self, stuff):
seen = set([])
for item in stuff:
if item == '.':
continue
if item in seen:
return False
seen.add(item)
return True
# Code (C++)
Approach 1:
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool rowVisited[9][9] = {false};
bool colVisited[9][9] = {false};
bool boxVisited[9][9] = {false};
for (int i = 0; i < board.size(); ++i)
{
for (int j = 0; j < board[0].size(); ++j)
{
if (board[i][j] == '.')
continue;
int digit = board[i][j] - '1';
int k = i / 3 * 3 + j / 3;
if (rowVisited[i][digit] || colVisited[j][digit] || boxVisited[k][digit])
return false;
rowVisited[i][digit] = true;
colVisited[j][digit] = true;
boxVisited[k][digit] = true;
}
}
return true;
}
};