/ Array

# Check If a Sudoku is Valid

##### Problem Statement

Determine if a sudoku is Valid.

###### Solution Explanation

Given a sudoku grid, we need to verify if the already filled in numbers doesn't violate the sudoku rules. The rules are very simple,

• Each row has numbers from 1-9 and no repitions
• Each column has numbers from 1-9 and no repitions
• Each 33 cube has numbers from 1-9

For example, given the below sudoku,

There are no rows or columns or 3*3 grid which violate the above rules.For validating the grid, we could use the following psuedocode:

``````    for i=0 to rowlen-1
declare rowset, colset, cubeset
for j=0 to collen-1
check if the grid[i][j] is in a row set, if yes, return false
check if the grid[j][i] is in a col set, if yes, return false
check if the neighbor cell in the grid is not present in cubeset,
if yes, return false
else add it to cube set

``````

We can do all this while traversing through the grid only once and below is the complete java implementation,

``````class ValidateSudoku {
public boolean isSudokuValid(char[][] board) {
if (board == null || board.length == 0)
return true;
int rowlen = board.length, collen = board[0].length;
for(int i=0;i<rowlen;i++){
Set<Character> rowSet = new HashSet<>();
Set<Character> colSet = new HashSet<>();
Set<Character> gridSet = new HashSet<>();
for(int j=0;j<collen;j++){
return false;
return false;
int RowIndex = 3*(i/3);
int ColIndex = 3*(i%3);
if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !gridSet.add(board[RowIndex + j/3][ColIndex + j%3]))
return false;
}
}

return true;

}
}
``````
###### Time Complexity

Since we traverse through the grid only once, the time complexity is O(n^2).