Dare2Solve
The problem requires us to check if a given partially filled 9x9 Sudoku board is valid. The key point is that we only need to validate the filled cells according to the Sudoku 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 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
By keeping track of the numbers seen so far in each row, column, and 3x3 sub-box, we can efficiently validate the board as we iterate through each cell.
Initialization:
Iterate through the board:
Loop through each cell in the 9x9 grid using nested loops for rows and columns.
For each cell that contains a number (not '.'), do the following:
Calculate the index of the corresponding 3x3 sub-box.
Check if the number already exists in the current row, column, or sub-box using the respective dictionaries.
If the number is already present in any of the dictionaries, the board is not valid, so return false
.
If the number is not present, mark it as seen in the respective dictionaries for the current row, column, and sub-box.
Return the result:
true
, indicating the Sudoku board is valid.O(1)
O(1)
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<unordered_map<char, bool>> rows(9);
vector<unordered_map<char, bool>> cols(9);
vector<unordered_map<char, bool>> boxes(9);
for (int r = 0; r < 9; ++r) {
for (int c = 0; c < 9; ++c) {
if (board[r][c] != '.') {
char num = board[r][c];
int boxIndex = (r / 3) * 3 + (c / 3);
if (rows[r][num] || cols[c][num] || boxes[boxIndex][num]) {
return false;}
rows[r][num] = true;
cols[c][num] = true;
boxes[boxIndex][num] = true;
}
}
}
return true;
}
};
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
rows = [{} for _ in range(9)]
cols = [{} for _ in range(9)]
boxes = [{} for _ in range(9)]
for r in range(9):
for c in range(9):
if board[r][c] != '.':
num = board[r][c]
box_index = (r // 3) * 3 + (c // 3)
if num in rows[r] or num in cols[c] or num in boxes[box_index]:
return False
rows[r][num] = True
cols[c][num] = True
boxes[box_index][num] = True
return True
class Solution {
public boolean isValidSudoku(char[][] board) {
HashMap<Character, Boolean>[] rows = new HashMap[9];
HashMap<Character, Boolean>[] cols = new HashMap[9];
HashMap<Character, Boolean>[] boxes = new HashMap[9];
for (int i = 0; i < 9; i++) {
rows[i] = new HashMap<>();
cols[i] = new HashMap<>();
boxes[i] = new HashMap<>();}
for (int r = 0; r < 9; r++) {
for (int c = 0; c < 9; c++) {
if (board[r][c] != '.') {
char num = board[r][c];
int boxIndex = (r / 3) * 3 + (c / 3);
if (rows[r].getOrDefault(num, false) || cols[c].getOrDefault(num, false) || boxes[boxIndex].getOrDefault(num, false)) {
return false;}
rows[r].put(num, true);
cols[c].put(num, true);
boxes[boxIndex].put(num, true);
}
}
}
return true;
}}
var isValidSudoku = function(board) {
let rows = new Array(9).fill(0).map(() => ({}))
let cols = new Array(9).fill(0).map(() => ({}))
let box = new Array(9).fill(0).map(() => ({}))
for(let r = 0; r < 9; r++){
for(let c = 0; c < 9; c++){
if(board[r][c] !== "."){
let num = board[r][c]
let boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3)
if(rows[r][num] || cols[c][num] || box[boxIndex][num]){
return false}
rows[r][num] = true
cols[c][num] = true
box[boxIndex][num] = true
}
}}
return true
};