In the Leetcode Valid Sudoku problem solution 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:
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 3×3 sub-box, it is invalid.
Constraints:
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit 1-9 or ‘.’.
Solution in C Programming
bool isValidSudoku(char** board, int boardSize, int* boardColSize){
for(int i=0; i<boardSize; i++){
int checkArr[9] = {0,0,0,0,0,0,0,0,0};
for(int j=0; j<boardSize; j++){
int currentIdx = (board[i][j]-'0') - 1;
if(board[i][j]-'0' > 0){ //if not '.'
if(checkArr[currentIdx] > 0){
return false;
}
checkArr[currentIdx]++;
}
}
}
for(int i=0; i<boardSize; i++){
int checkArr[9] = {0,0,0,0,0,0,0,0,0};
for(int j=0; j<boardSize; j++){
int currentIdx = (board[j][i]-'0') - 1;
if(board[j][i]-'0' > 0){
if(checkArr[currentIdx] > 0){
return false;
}
checkArr[currentIdx]++;
}
}
}
for(int row=1; row<=3; row++){
for(int col=1; col<=3; col++){
int checkArr[9] = {0,0,0,0,0,0,0,0,0};
for(int r = row*3-3; r<row*3; r++){
for(int c = col*3-3; c<col*3; c++){
if(board[r][c]-'0' > 0){ //check if number or '.'
int currentIdx = (board[r][c]-'0') - 1;
if(checkArr[currentIdx] > 0){
return false;
}
checkArr[currentIdx]++;
}
}
}
}
}
return true;
}Solution in C++ Programming
class Solution{
public:
bool isValidSudoku(vector<vector<char>> &board){
int used1[9][9] = {0}, used2[9][9] = {0}, used3[9][9] = {0};
// flag for ith row , column and grid
for(int i = 0; i < board.size(); ++ i) // travel the row
for(int j = 0; j < board[i].size(); ++ j) // travel the columns
if(board[i][j] != '.'){ // if there is a value
int num = board[i][j] - '0' - 1; // -1 just to match array index
int k = (i / 3) * 3 + (j / 3);
// say in 0 to 8 grids, 4th grid is from i = 3,4,5 and j =3,4,5
if(used1[i][num] || used2[j][num] || used3[k][num])
return false;
// already a ith no is there in that row,col,grid
used1[i][num] = used2[j][num] = used3[k][num] = 1;
// put a flag in that row,col,grid
}
return true;
}
};
Solution in Java Programming
class Solution {
public boolean isValidSudoku(char[][] board) {
List<boolean[]> subBoxCheckList = fillBooleanList(3);
List<boolean[]> colmsCheckList = fillBooleanList(9);
boolean[] row;
for(int i = 0; i < board.length; i++){
row = new boolean[10];
for(int j = 0; j < board.length; j++){
if(board[i][j] != '.') {
if(row[board[i][j] - 48]) {
return false;
}
else row[board[i][j] - 48] = true;
if(colmsCheckList.get(j)[board[i][j] - 48]) {
return false;
}
else colmsCheckList.get(j)[board[i][j] - 48] = true;
int subBoxIndex = (j / 3);
if(subBoxCheckList.get(subBoxIndex)[board[i][j] - 48]) {
return false;
}
else {
subBoxCheckList.get(subBoxIndex)[board[i][j] - 48] = true;
}
}
}
if((i + 1) % 3 == 0) subBoxCheckList = fillBooleanList(3);
}
return true;
}
private List<boolean[]> fillBooleanList(int size){
List<boolean[]> list = new ArrayList<>();
while(size != 0){
list.add(new boolean[10]);
size--;
}
return list;
}
}Solution in Python Programming
class Solution(object):
def isValidSudoku(self, board):
row = collections.defaultdict(set)
col = collections.defaultdict(set)
sqr = collections.defaultdict(set)
for r in range(9):
for c in range(9):
if board[r][c] != '.':
if(board[r][c] in row[r] or board[r][c] in col[c] or board[r][c] in sqr[(r//3, c//3)]):
return False
row[r].add(board[r][c])
col[c].add(board[r][c])
sqr[(r//3, c//3)].add(board[r][c])
return TrueSolution in C# Programming
public class Solution {
public bool IsValidSudoku(char[][] board) {
var totalRow = board.Length;
var totalCol = board[0].Length;
var dictRow = new Dictionary<int,HashSet<int>>();
var dictCol = new Dictionary<int,HashSet<int>>();
var dictBoxIndex = new Dictionary<int,HashSet<int>>();
for(int i=0;i<9;i++){
dictRow.Add(i+1, new HashSet<int>());
dictCol.Add(i+1, new HashSet<int>());
dictBoxIndex.Add(i, new HashSet<int>());
}
for(int r=0;r<totalRow;r++){
for(int c=0;c<totalCol;c++){
var box_index = (r/3) * 3 + c/3;
var num = board[r][c]-'0';
if(num != -2 && (!dictRow[r+1].Add(num) || !dictCol[c+1].Add(num)
|| !dictBoxIndex[box_index].Add(num)))
{
return false;
}
}
}
return true;
}
} Also read,