LeetCode - 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:

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

Constraints:

- board.length == 9
- board[i].length == 9
- board[i][j] is a digit 1-9 or '.'

Explanation

The problem requires us to verify if the Sudoku board is valid or not. The approach to solving the problem will be similar to the way we fill the Sudoku. We check every row, column and 3 x 3 cell to verify if they contain any duplicate numbers.

Let's check the algorithm directly.

// isValidSudoku function
- initialize i

- for every row verify if it's valid
  loop for i = 0; i < 9; i++
    - if !isValidRow(board[i])
      - return false

- for every column verify if it's valid
  loop for i = 0; i < 9; i++
    - if !isValidColumn(board, i)
      - return false

- for every cell in sudoku verify if it's valid
  loop for = 0; i < 9; i = i + 3
    for j = 0; j < 9; j = j + 3
      - if !isValidCell(board, i, j)
        - return false

// isValidRow function
- set checker = 0
  initialize num

- loop for i = 0; i < 9; i++
  - if row[i] != '.'
    - set num = row[i] - '0'
    - if checker & (1 << num) > 0
      - return false
    - checker = checker | (1 << num)

- return true

// isValidColumn function
- set checker = 0
  initialize num

- loop for i = 0; i < 9; i++
  - if board[i][j] != '.'
    - set num = board[i][j] - '0'
    - if checker & (1 << num) > 0
      - return false
    - checker = checker | (1 << num)

- return true

// isValidCell function
- set checker = 0
  initialize num

- loop for i = n; i < n + 3; i++
  - loop for j = m; j < m + 3; j++
    - if board[i][j] != '.'
      - set num = board[i][j] - '0'
      - if checker & (1 << num) > 0
        - return false
      - checker = checker | (1 << num)

- return true

C++ solution

class Solution {
static bool isValidRow(vector<char>& row){
    int checker = 0, num;

    for(int i = 0; i < 9; i++){
        if(row[i] != '.'){
            num = row[i] - '0';
            if((checker & (1 << num)) > 0)
                return false;
            checker = (checker | (1 << num));
        }
    }

    return true;
};

static bool isValidColumn(vector<vector<char>>& board, int j){
    int checker = 0, num;

    for(int i = 0; i < 9; i++){
        if(board[i][j] != '.'){
            num = board[i][j] - '0';
            if((checker & (1 << num)) > 0)
                return false;
            checker = (checker | (1 << num));
        }
    }

    return true;
};

static bool isValidCell(vector<vector<char>>& board, int n, int m){
    int checker = 0, num;

    for(int i = n; i < n + 3; i++){
        for(int j = m; j < m + 3; j++){
            if(board[i][j] != '.'){
                num = board[i][j] - '0';
                if((checker & (1 << num)) > 0)
                    return false;
                checker = (checker | (1 << num));
            }
        }
    }

    return true;
};

public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int i;

        for(i = 0; i < 9; i++){
            if(!isValidRow(board[i])){
                return false;
            }
        }

        for(i = 0; i < 9; i++){
            if(!isValidColumn(board, i)){
                return false;
            }
        }

        for(i = 0; i < 9; i += 3){
            for(int j = 0; j < 9; j += 3){
               if(!isValidCell(board, i, j)){
                    return false;
                }
            }
        }

        return true;
    }
};

Golang solution

func isValidRow(board []byte) bool {
    checker, num := 0, 0

    for i := 0; i < 9; i++ {
        if board[i] != '.' {
            num = int(board[i] - '0')
            if checker & (1 << num) != 0 {
                return false
            }

            checker = checker | (1 << num)
        }
    }

    return true
}

func isValidColumn(board [][]byte, j int) bool {
    checker, num := 0, 0

    for i := 0; i < 9; i++ {
        if board[i][j] != '.' {
            num = int(board[i][j] - '0')
            if checker & (1 << num) != 0 {
                return false
            }

            checker = checker | (1 << num)
        }
    }

    return true
}

func isValidCell(board [][]byte, n, m int) bool {
    checker, num := 0, 0

    for i := n; i < n + 3; i++ {
        for j := m; j < m + 3; j++ {
            if board[i][j] != '.' {
                num = int(board[i][j] - '0')
                if checker & (1 << num) != 0 {
                    return false
                }

                checker = checker | (1 << num)
            }
        }
    }

    return true
}

func isValidSudoku(board [][]byte) bool {
    for i := 0; i < 9; i++ {
        if !isValidRow(board[i]) {
            return false
        }
    }

    for i := 0; i < 9; i++ {
        if !isValidColumn(board, i) {
            return false
        }
    }

    for i := 0; i < 9; i += 3 {
        for j := 0; j < 9; j += 3 {
            if !isValidCell(board, i, j) {
                return false
            }
        }
    }

    return true
}

Javascript solution

var isValidRow = function(board) {
    let checker = 0, num;

    for(let i = 0; i < 9; i++){
        if(board[i] != '.'){
            num = board[i] - '0';
            if((checker & (1 << num)) > 0)
                return false;
            checker = (checker | (1 << num));
        }
    }

    return true;
}

var isValidColumn = function(board, j) {
    let checker = 0, num;

    for(let i = 0; i < 9; i++){
        if(board[i][j] != '.'){
            num = board[i][j] - '0';
            if((checker & (1 << num)) > 0)
                return false;
            checker = (checker | (1 << num));
        }
    }

    return true;
}

var isValidCell = function(board, n, m) {
    let checker = 0, num;

    for(let i = n; i < n + 3; i++){
        for(let j = m; j < m + 3; j++){
            if(board[i][j] != '.'){
                num = board[i][j] - '0';
                if((checker & (1 << num)) > 0)
                    return false;
                checker = (checker | (1 << num));
            }
        }
    }

    return true;
}

var isValidSudoku = function(board) {
    let i;

    for(i = 0; i < 9; i++){
        if(!isValidRow(board[i])){
            return false;
        }
    }

    for(i = 0; i < 9; i++){
        if(!isValidColumn(board, i)){
            return false;
        }
    }

    for(i = 0; i < 9; i += 3){
        for(let j = 0; j < 9; j += 3){
           if(!isValidCell(board, i, j)){
                return false;
            }
        }
    }

    return true;
};

Let's dry-run just one row to get an idea of how it validates every column and cell.

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"]]

// isValidSudoku function

Step 1: initialize i

Step 2: for(i = 0; i < 9; i++){
           if(!isValidRow(board[i])){
               return false;
            }
        }

// we will only check for the first 0th row
// in isValidRow

Step 3: set checker = 0
        initialize num

        loop for i = 0; i < 9; i++
          - if board[i] != '.'
            board[0] != '.'
            '5' != '.'
            true

            num = board[i] - '0'
                = '5' - '0'
                = 5

            if checker & (1 << num) > 0
               0 & (1 << 5) > 0
               0 > 0
               false

            checker = (checker | (1 << num))
                    = 0 | 1 << 5
                    = 0 | 32
                    = 32

            i++
            i = 1

Step 4: i < 9
        1 < 9
        true

        - if board[i] != '.'
          board[1] != '.'
          '3' != '.'
          true

        num = board[i] - '0'
            = '3' - '0'
            = 3

        if checker & (1 << num) > 0
           0 & (1 << 3) > 0
           0 > 0
           false

        checker = (checker | (1 << num))
                = 32 | 1 << 3
                = 32 | 8
                = 40

        i++
        i = 2

Step 5: i < 9
        2 < 9
        true

        - if board[i] != '.'
          board[2] != '.'
          '.' != '.'
          false

        i++
        i = 3

Step 6: i < 9
        3 < 9
        true

        - if board[i] != '.'
          board[3] != '.'
          '.' != '.'
          false

        i++
        i = 4

Step 7: i < 9
        4 < 9
        true

        - if board[i] != '.'
          board[4] != '.'
          '7' != '.'
          true

        num = board[i] - '0'
            = '7' - '0'
            = 7

        if checker & (1 << num) > 0
           0 & (1 << 7) > 0
           0 > 0
           false

        checker = (checker | (1 << num))
                = 40 | 1 << 7
                = 40 | 128
                = 168

        i++
        i = 5

Step 8: i < 9
        5 < 9
        true

        - if board[i] != '.'
          board[5] != '.'
          '.' != '.'
          false

        i++
        i = 6

Step 9: i < 9
        6 < 9
        true

        - if board[i] != '.'
          board[6] != '.'
          '.' != '.'
          false

        i++
        i = 7

Step 10: i < 9
         7 < 9
         true

         - if board[i] != '.'
           board[7] != '.'
           '.' != '.'
           false

         i++
         i = 8

Step 11: i < 9
         8 < 9
         true

         - if board[i] != '.'
           board[8] != '.'
           '.' != '.'
           false

         i++
         i = 9

Step 12: i < 9
         9 < 9
         false

Step 13: return true

So we calculate the answer in the same way for the rest of the rows, columns, and 3 x 3 cells.

For this 9 x 9 matrix, the answer is true. The answer we return is true.

Blog

LeetCode - Valid Sudoku

Alkesh Ghorpade

Problem statement

Explanation

C++ solution

Golang solution

Javascript solution

Join Our Newsletter. No Spam, Only the good stuff.

Related