Valid Suduko Problem: 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 digits1-9
without repetition.
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
Table of Contents
Valid Suduko Problem Solution
Problem Solution In Python
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
def is_valid_row():
for row in board:
if not is_valid(row):
return False
return True
def is_valid_col():
for col in zip(*board):
if not is_valid(col):
return False
return True
def is_valid_square():
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 is_valid(square):
return False
return True
def is_valid(value):
res=[i for i in value if i!="."]
return len(res)==len(set(res))
return is_valid_row() and is_valid_col() and is_valid_square()
Problem Solution In Java
class Solution {
public boolean isValidSudoku(char[][] board) {
int n = board.length;
Set<Integer>[] rows = new Set[n];
Set<Integer>[] cols = new Set[n];
Set<Integer>[] blocks = new Set[n];
for(int i = 0; i < n; i++) {
rows[i] = new HashSet<Integer>();
cols[i] = new HashSet<Integer>();
blocks[i] = new HashSet<Integer>();
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == '.') continue;
int k = 3 * (i /3) + (j / 3);
int num = board[i][j] - '0';
if (rows[i].contains(num)) return false;
if (cols[j].contains(num)) return false;
if (blocks[k].contains(num)) return false;
rows[i].add(num);
cols[j].add(num);
blocks[k].add(num);
}
}
return true;
}
}
Problem Solution In C++
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<set<int>> rows(9), cols(9), blocks(9);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') continue;
int curr = board[i][j] - '0';
if (rows[i].count(curr) || cols[j].count(curr) || blocks[(i/3)*3+j/3].count(curr))
return false;
rows[i].insert(curr);
cols[j].insert(curr);
blocks[(i/3)*3+j/3].insert(curr);
}
}
return true;
}
};
Problem Solution In C
bool isValidSudoku(char** board, int boardSize, int* boardColSize){
int i=0, j=0;
int rowSet[9][10] = {0};
int colSet[9][10] = {0};
int box[3][3][10] = {0};
for(i = 0; i<9; i++){
for(j=0; j<9; j++){
if(board[i][j] != '.'){
int val = (int)board[i][j] - 48;//Converting to int
if(rowSet[i][val] != 0)
return false;
if(colSet[j][val] != 0)
return false;
if(box[i/3][j/3][val] !=0)
return false;
box[i/3][j/3][val] +=1;
rowSet[i][val] +=1;
colSet[j][val] +=1;
}
}
}
return true;
}