Valid Sudoku Leetcode


#1

Determine if a 9x9 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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.


A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["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:
[
  ["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.

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.
  • The given board contain only digits 1-9 and the character '.'.
  • The given board size is always 9x9.

#2

We basically traverse the whole grid checking row, column and grid for any duplicate elements. The trick here is to understand the formula required to traverse the 3*3 grid in a single pass.

func isValidSudoku(board [][]byte) bool {
    for i:=0; i<len(board); i++{
        rowMap := make(map[byte]bool, 0)
        colMap := make(map[byte]bool, 0)
        gridMap := make(map[byte]bool, 0)
        
        for j:=0; j<len(board); j++{
            // row validation
            if board[i][j]!='.' && rowMap[board[i][j]]{
                return false
            } else {
                rowMap[board[i][j]] = true
            }
            
            // column validation
            if board[j][i]!='.' && colMap[board[j][i]]{
                return false
            } else {
                colMap[board[j][i]] = true
            }
            
            // 3*3 grid validation
            rowIndex := 3*(i/3)
            colIndex := 3*(i%3)
            
            if board[rowIndex+j/3][colIndex+j%3]!='.' && gridMap[board[rowIndex+j/3][colIndex+j%3]] {
                return false
            } else {
                gridMap[board[rowIndex+j/3][colIndex+j%3]] = true
            }
        }
    }
    
    return true
}


// Workbook

// 1. Traverse through the grid, check for repetitions on a row level, column level, grid level.
// 2. row - i, j
// 3. column - j, i
//     0 1 2 3 4 5 .. 9
// 0
// 1
// 2
// 3
// 4
// 5
// 6

// i - 0 to 9
// j - 0 to 9

// row index - 3*(i/3)
// col index - 3*(i%3)

// rowindex+j/3, colIndex+j%3

// i j ri ci rivalue civalue
// 0 0 0  0   0       0
// 0 1 0  0   0       1
// 0 2 0  0   0       2
// 0 3 0

// 0 0
// 0 1
// 0 2
// 1 0
// 1 1
// 1 2
// 2 0
// 2 1
// 2 2