# Problem - Leetcode

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 1:**

```
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
```

**Example 2:**

```
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
3x3 sub-box, it is invalid.
```

**Constraints:**

`board.length == 9`

`board[i].length == 9`

`board[i][j]`

is a digit`1-9`

or`'.'`

.

# Answer-1 in Golang

```
func isValidSudoku(board [][]byte) bool {
hashMap := make(map[string]bool)
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
row := i
column := j
current_val := string(board[i][j])
if current_val == "." {
continue
}
_, ok1 := hashMap[current_val+"row"+string(row)]
_, ok2 := hashMap[current_val+"col"+string(column)]
_, ok3 := hashMap[current_val+"gri"+string(i/3)+string(j/3)]
if ok1 || ok2 || ok3 {
return false
} else {
hashMap[current_val+"row"+string(row)] = true
hashMap[current_val+"col"+string(column)] = true
hashMap[current_val+"gri"+string(i/3)+string(j/3)] = true
}
}
}
return true
}
```

This code defines a function called `isValidSudoku`

which takes a 2D grid of characters (`board`

), representing a Sudoku puzzle, and checks whether the given puzzle is a valid Sudoku configuration or not. The function returns a boolean value (`true`

if the Sudoku is valid, otherwise `false`

).

Here's a detailed breakdown of the code:

`hashMap`

is initialized as a map that will be used to keep track of the presence of digits in different rows, columns, and subgrids.The code uses two nested loops to iterate over each cell of the 9x9 Sudoku board.

For each cell, the row and column indices (

`i`

and`j`

) are extracted.The value in the current cell (

`current_val`

) is converted to a string.If the

`current_val`

is a dot (`"."`

), indicating an empty cell, the code continues to the next iteration, as an empty cell is always considered valid.The code checks three conditions to determine the validity of the Sudoku puzzle:

`ok1`

: Checks if the current value exists in the same row.`ok2`

: Checks if the current value exists in the same column.`ok3`

: Checks if the current value exists in the same 3x3 subgrid.

If any of the three conditions (

`ok1`

,`ok2`

, or`ok3`

) is true, it means that the current value violates the Sudoku rules, and the function returns`false`

, indicating an invalid Sudoku configuration.If all three conditions are false, it means that the current value is valid within its row, column, and subgrid. The code then updates the

`hashMap`

by setting the corresponding entries to`true`

for the current value in the current row, column, and subgrid.The loops continue until all cells in the 9x9 board have been processed.

If the loops complete without returning

`false`

, it means that all values in the Sudoku board are valid according to the rules of Sudoku, and the function returns`true`

.

In summary, the code iterates through each cell in the Sudoku board, using a `hashMap`

to keep track of digits in rows, columns, and subgrids. It checks if the current value violates any Sudoku rules by looking at the `hashMap`

. If any violation is found, it returns `false`

; otherwise, if all values are valid, it returns `true`

. This code effectively determines whether a given Sudoku puzzle configuration is valid or not.

# Answer-2 Top Runtime in Golang

```
func isValidSudoku(board [][]byte) bool {
rowFlags := [9][9]bool{}
colFlags := [9][9]bool{}
boxFlags := [9][9]bool{}
for i, row := range board {
for j, b := range row {
if '.' == b {
continue
}
n := b - '1'
if rowFlags[i][n] {
return false
}
rowFlags[i][n] = true
if colFlags[j][n] {
return false
}
colFlags[j][n] = true
if boxFlags[i/3*3+j/3][n] {
return false
}
boxFlags[i/3*3+j/3][n] = true
}
}
return true
}
```

This code is an implementation of a function called `isValidSudoku`

that checks whether a given Sudoku board is valid or not. A valid Sudoku board follows the rules of Sudoku: each row, column, and the 3x3 subgrids (referred to as "boxes") within the board should contain the digits 1 through 9 without repetition.

Here's a detailed breakdown of how the code works:

The function

`isValidSudoku`

takes a 2D array (`board`

) of bytes as its input parameter. This array represents the Sudoku board.Three 2D arrays,

`rowFlags`

,`colFlags`

, and`boxFlags`

, are initialized. These arrays are used to keep track of whether a digit from 1 to 9 has already been encountered in the corresponding row, column, or box.Two nested loops iterate through each cell of the

`board`

. The outer loop iterates through each row (`i`

), and the inner loop iterates through each cell within the row (`j`

).For each cell (

`i`

,`j`

), the code checks if the character at that position in the`board`

is a dot ('.'). If it is a dot, it means the cell is empty, so the code continues to the next iteration.If the character is not a dot, it's assumed to be a digit (1 to 9). The digit is converted to an integer (

`n`

) by subtracting the ASCII value of '1'.The code then checks whether the digit

`n`

has already appeared in the same row (`i`

), column (`j`

), or box (`i/3*3+j/3`

) using the respective flag arrays.If the digit

`n`

has already been flagged in any of the row, column, or box, it means the Sudoku rules are violated, and the function returns`false`

, indicating that the Sudoku board is not valid.If the digit

`n`

has not been encountered in any of the corresponding row, column, or box, the code sets the respective flag to`true`

to indicate that the digit has been encountered.The loops continue iterating through the entire board, checking each cell's digit against the flags.

If the loops complete without encountering any violations, the function returns

`true`

, indicating that the Sudoku board is valid.

In summary, the code uses three sets of flag arrays to keep track of the digits encountered in rows, columns, and boxes while iterating through the Sudoku board. If any digit is encountered more than once in the same row, column, or box, the function returns `false`

. Otherwise, it returns `true`

to indicate that the Sudoku board is valid according to the rules.

# Answer-3 Top Memory in Golang

```
func isValidSudoku(board [][]byte) bool {
res := true
res = res && validateRow(board)
res = res && validateCol(board)
res = res && validateGroup(board)
return res
}
func validateRow(board [][]byte) bool {
for i := 0; i < 9; i++ {
seen := make(map[byte]bool)
for j := 0; j < 9; j++ {
if board[i][j] != '.' {
if seen[board[i][j]] {
return false
}
seen[board[i][j]] = true
}
}
}
return true
}
func validateCol(board [][]byte) bool {
for j := 0; j < 9; j++ {
seen := make(map[byte]bool)
for i := 0; i < 9; i++ {
if board[i][j] != '.' {
if seen[board[i][j]] {
return false
}
seen[board[i][j]] = true
}
}
}
return true
}
func validateGroup(board [][]byte) bool {
for i := 0; i < 9; i+=3 {
for j := 0; j < 9; j+=3 {
// top left corner of one group
seen := make(map[byte]bool)
for xi := 0; xi < 3; xi ++ {
for xj := 0; xj < 3; xj ++ {
cell := board[i+xi][j+xj]
if cell != '.' {
if seen[cell] {
return false
}
seen[cell] = true
}
}
}
}
}
return true
}
```

This code is an implementation of a function to validate a Sudoku board. A Sudoku board is a 9x9 grid where each cell can contain a digit from 1 to 9 or a dot ('.') representing an empty cell. The rules for a valid Sudoku are that each row, each column, and each of the nine 3x3 subgrids that compose the board must contain distinct digits from 1 to 9.

Here's a breakdown of how the code works:

The main

`isValidSudoku`

function is the entry point. It checks the validity of the Sudoku board by calling three helper functions:`validateRow`

,`validateCol`

, and`validateGroup`

, and then returns the result.The

`validateRow`

function checks each row of the board. It iterates through each row and maintains a map called`seen`

to keep track of the digits encountered in that row. If a digit is encountered that's already in the`seen`

map, it means there's a duplicate digit in the row, and the function returns`false`

. Otherwise, it marks the digit as seen and continues to the next cell. If all cells in a row satisfy the rules, the function returns`true`

.The

`validateCol`

function checks each column of the board. Similar to`validateRow`

, it iterates through each column while maintaining a`seen`

map to track encountered digits. If a duplicate digit is found in a column, the function returns`false`

. Otherwise, it continues checking all cells in that column. If all columns pass the validation, the function returns`true`

.The

`validateGroup`

function checks each of the nine 3x3 subgrids (groups) in the Sudoku board. It uses two nested loops to iterate through the top left corner cell of each group. Within each group, it maintains a`seen`

map to track the digits encountered. If a duplicate digit is found within a group, the function returns`false`

. If all cells within all groups are validated, the function returns`true`

.

The main `isValidSudoku`

function combines the results of the three helper functions by using the `&&`

operator. If any of the helper functions returns `false`

, the entire board is considered invalid, and the function returns `false`

. If all three helper functions return `true`

, the board is valid, and the function returns `true`

.

In summary, this code snippet efficiently checks the validity of a Sudoku board by validating each row, each column, and each group separately. If all three aspects of the board meet the Sudoku rules, the board is considered valid.