# Solution For Valid Sudoku

Problem Statement:

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. 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.

Solution:

The problem statement is quite clear, we are given a 9×9 Sudoku board with partially filled cells, and we need to determine whether the given Sudoku board is valid or not.

We can iterate over the given board and check the validity of each row, each column, and each 3×3 sub-box. We can use a set to keep track of the digits 1-9 for each row, column, and sub-box. If we encounter a repeated digit, we can return False.

The first step is to iterate over the board and validate each row:

`def is_valid_sudoku(board) -> bool: for row in board: nums = set() for num in row: if num in nums: return False if num != ".": nums.add(num) return True`

Next, we need to validate each column. We can use the `zip()` function to transpose the board so that we can iterate over each column:

“`
def is_valid_sudoku(board) -> bool:
for row in board:
nums = set()
for num in row:
if num in nums:
return False
if num != “.”:

``````for col in zip(*board):
nums = set()
for num in col:
if num in nums:
return False
if num != ".":
return True
``````

“`

Finally, we need to validate each 3×3 sub-box. We can use nested loops to iterate over each sub-box. To determine the sub-box boundaries, we can use integer division to get the indices of the starting row and column of each sub-box:

“`
def is_valid_sudoku(board) -> bool:
for row in board:
nums = set()
for num in row:
if num in nums:
return False
if num != “.”:

``````for col in zip(*board):
nums = set()
for num in col:
if num in nums:
return False
if num != ".":

for i in range(0, 9, 3):
for j in range(0, 9, 3):
nums = set()
for k in range(3):
for l in range(3):
num = board[i+k][j+l]
if num in nums:
return False
if num != ".":
return True
``````

“`

Finally, we can combine all the above code snippets in a single function:

“`
def is_valid_sudoku(board) -> bool:
for row in board:
nums = set()
for num in row:
if num in nums:
return False
if num != “.”:

``````for col in zip(*board):
nums = set()
for num in col:
if num in nums:
return False
if num != ".":

for i in range(0, 9, 3):
for j in range(0, 9, 3):
nums = set()
for k in range(3):
for l in range(3):
num = board[i+k][j+l]
if num in nums:
return False
if num != ".":
return True
``````

“`

Note that we are checking all three conditions in a single pass, so the time complexity is O(81) = O(1). The space complexity is also constant, so the solution is quite efficient.

## Step by Step Implementation For Valid Sudoku

```public boolean isValidSudoku(char[][] board) {
// init data
HashMap [] rows = new HashMap[9];
HashMap [] columns = new HashMap[9];
HashMap [] boxes = new HashMap[9];
for (int i = 0; i < 9; i++) {
rows[i] = new HashMap();
columns[i] = new HashMap();
boxes[i] = new HashMap();
}

// validate a board
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char num = board[i][j];
if (num != '.') {
int n = (int)num;
int box_index = (i / 3 ) * 3 + j / 3;

// keep the current cell value
rows[i].put(n, rows[i].getOrDefault(n, 0) + 1);
columns[j].put(n, columns[j].getOrDefault(n, 0) + 1);
boxes[box_index].put(n, boxes[box_index].getOrDefault(n, 0) + 1);

// check if this value has been already seen before
if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1)
return false;
}
}
}

return true;
}```
```class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:

# check each row
for row in board:
if not self.isValidList(row):
return False

# check each column
for i in range(9):
column = [row[i] for row in board]
if not self.isValidList(column):
return False

# check each 3x3 sub-grid
for i in range(0, 9, 3):
for j in range(0, 9, 3):
subgrid = [board[x][y] for x in range(i, i+3) for y in range(j, j+3)]
if not self.isValidList(subgrid):
return False

return True

def isValidList(self, lst: List[str]) -> bool:
seen = set()
for i in lst:
if i != '.':
if i in seen:
return False
return True```
```/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function(board) {
// check each column
for(let i = 0; i < 9; i++) {
let seen = {};
for(let j = 0; j < 9; j++) {
let num = board[j][i];
if(num !== '.') {
if(seen[num]) {
return false;
}
seen[num] = true;
}
}
}

// check each row
for(let i = 0; i < 9; i++) {
let seen = {};
for(let j = 0; j < 9; j++) {
let num = board[i][j];
if(num !== '.') {
if(seen[num]) {
return false;
}
seen[num] = true;
}
}
}

// check each 3 x 3 subgrid
for(let i = 0; i < 9; i++) {
let seen = {};
for(let j = 0; j < 9; j++) {
let r = Math.floor(i / 3) * 3 + Math.floor(j / 3);
let c = i * 3 % 9 + j % 3;
let num = board[r][c];
if(num !== '.') {
if(seen[num]) {
return false;
}
seen[num] = true;
}
}
}

return true;
};```
```bool isValidSudoku(vector>& board) {

// check each row
for(int i = 0; i < 9; i++){
unordered_set row;
for(int j = 0; j < 9; j++){
if(board[i][j] == '.') continue;
if(row.count(board[i][j])) return false;
row.insert(board[i][j]);
}
}

// check each column
for(int j = 0; j < 9; j++){
unordered_set col;
for(int i = 0; i < 9; i++){
if(board[i][j] == '.') continue;
if(col.count(board[i][j])) return false;
col.insert(board[i][j]);
}
}

// check each sub-matrix
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
unordered_set subMatrix;
for(int k = 0; k < 3; k++){
for(int l = 0; l < 3; l++){
if(board[3*i+k][3*j+l] == '.') continue;
if(subMatrix.count(board[3*i+k][3*j+l])) return false;
subMatrix.insert(board[3*i+k][3*j+l]);
}
}
}
}
return true;
}```
```public class Solution {
public bool IsValidSudoku(char[][] board) {
//validate row
for(int i = 0; i < 9; i++){
HashSet row = new HashSet();
for(int j = 0; j < 9; j++){
return false;
}
}

//validate column
for(int j = 0; j < 9; j++){
HashSet column = new HashSet();
for(int i = 0; i < 9; i++){
return false;
}
}

//validate 3*3 matrix
for(int block = 0; block < 9; block++){
HashSet threeByThree = new HashSet();
for(int i = block / 3 * 3; i < block / 3 * 3 + 3; i++){
for(int j = block % 3 * 3; j < block % 3 * 3 + 3; j++){