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:

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.

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:

1. hashMap is initialized as a map that will be used to keep track of the presence of digits in different rows, columns, and subgrids.

2. The code uses two nested loops to iterate over each cell of the 9x9 Sudoku board.

3. For each cell, the row and column indices (i and j) are extracted.

4. The value in the current cell (current_val) is converted to a string.

5. 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.

6. 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.

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

8. 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.

9. The loops continue until all cells in the 9x9 board have been processed.

10. 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:

1. The function isValidSudoku takes a 2D array (board) of bytes as its input parameter. This array represents the Sudoku board.

2. 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.

3. 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).

4. 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.

5. 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'.

6. 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.

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

8. 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.

9. The loops continue iterating through the entire board, checking each cell's digit against the flags.

10. 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:

1. 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.

2. 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.

3. 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.

4. 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.