#36 Leetcode Valid Sudoku Solution in C, C++, Java, JavaScript, Python, C# Leetcode

Algorithm

Problem Name: 36. Valid Sudoku

Problem Link: https://leetcode.com/problems/valid-sudoku/

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

Code Examples

#1 Code Example with C Programming

Code - C Programming


#define VERIFY_HASH(I, J) do { \
    c = board[I][J]; \
    if (c >= '1' && c  < = '9') { \
        b = 1 << (c - '1'); \
        if (hash & b) return false; \
        hash |= b; \
    }\
} while (0)

#define IDX(I, J) ((I) / 3 * (boardColSize + 2) / 3 + (J) / 3)

bool isValidSudoku(char** board, int boardRowSize, int boardColSize) {
    int hash;
    int i, j, m, n;
    char c;
    int b;
    
    int *hc, *hs, *buff;
    buff = calloc((boardColSize + ((boardRowSize + 2) / 3 * (boardColSize + 2) / 3)), sizeof(int));
    //assert(buff);
    hc = &buff[0];
    hs = &buff[boardColSize];
    
    for (i = 0; i  <  boardRowSize; i ++) {
        hash = 0;
        for (j = 0; j  <  boardColSize; j ++) {
            c = board[i][j];
            if (c  <  '1' || c > '9') continue;
            b = 1 << (c - '1');
            if ((hash & b) ||           // verify failed on current line
                (hc[j] & b) ||          // verify failed on current column
                (hs[IDX(i, j)] & b)) {  // failed on current nestled square
                free(buff);
                return false;
            }
            hash |= b;
            hc[j] |= b;
            hs[IDX(i, j)] |= b;
        }
    }
    free(buff);
    
    return true;
}

Copy The Code & Try With Live Editor

Input

–

cmd

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

–

cmd

true

#2 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int n = board.size();
        vector < unordered_mapsub(n/3, vector < unordered_map 0 || col[j][c]++ > 0 || sub[i/3][j/3][c]++ > 0) return false;
            }
        return true;
    }
};

Copy The Code & Try With Live Editor

Input

–

cmd

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

–

cmd

false

#3 Code Example with Java Programming

Code - Java Programming


class Solution {
  public boolean isValidSudoku(char[][] board) {
    int N = 9;
    int[][] rows = new int[N][N];
    int[][] cols = new int[N][N];
    int[][] boxes = new int[N][N];
    for (int r = 0; r  <  N; r++) {
      for (int c = 0; c  <  N; c++) {
        if (board[r][c] == '.') {
          continue;
        }
        int pos = board[r][c] - '1';
        if (rows[r][pos] == 1) {
          return false;
        }
        rows[r][pos] = 1;
        if (cols[c][pos] == 1) {
          return false;
        }
        cols[c][pos] = 1;
        int idx = (r / 3) * 3 + c / 3;
        if (boxes[idx][pos] == 1) {
          return false;
        }
        boxes[idx][pos] = 1;
      }
    }
    return true;
  }
}

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

true

#4 Code Example with Javascript Programming

Code - Javascript Programming


const isValidSudoku = function(board) {
  const n = 9
  const m = 3
  const row = [],
    col = [],
    block = []
  for (let i = 0; i  <  n; i++) {
    row[i] = new Set()
    col[i] = new Set()
    block[i] = new Set()
  }
  for (let r = 0; r  <  n; r++) {
    for (let c = 0; c  <  n; c++) {
      const ch = board[r][c]
      if (ch === '.') continue
      const b = Math.floor(r / m) * m + Math.floor(c / m)
      if (row[r].has(ch) || col[c].has(ch) || block[b].has(ch)) return false
      row[r].add(ch)
      col[c].add(ch)
      block[b].add(ch)
    }
  }
  return true
}

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

false

#5 Code Example with Python Programming

Code - Python Programming


class Solution:
    def isValidSudoku(self, board):
        rows, cols, triples = collections.defaultdict(set), collections.defaultdict(set), collections.defaultdict(set)
        for i, row in enumerate(board):
            for j, c in enumerate(row):
                if c != "." and c in rows[i] or c in cols[j] or c in triples[(i //3, j // 3)]: 
                    return False
                elif c != ".": 
                    rows[i].add(c); cols[j].add(c); triples[(i // 3, j // 3)].add(c)
        return True

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

false

#6 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _036_ValidSudoku
    {
        public bool IsValidSudoku(char[,] board)
        {
            int row, column, squareId, value;
            var colUsed = new bool[9, 9];
            var rowUsed = new bool[9, 9];
            var squareUsed = new bool[9, 9];

            for (row = 0; row  <  9; row++)
            {
                for (column = 0; column  <  9; column++)
                {
                    value = board[row, column] - '0' - 1;
                    if (value > 8 || value  <  0) { continue; }
                    squareId = (row / 3) * 3 + column / 3;
                    if (colUsed[column, value] || rowUsed[row, value] || squareUsed[squareId, value]) { return false; }

                    colUsed[column, value] = rowUsed[row, value] = squareUsed[squareId, value] = true;
                }
            }

            return true;
        }
    }
}

Copy The Code & Try With Live Editor

Input

–

cmd

Output

–

cmd

true

Demonstration

Previous
#35 Leetcode - Search Insert Position Problem Solution in Javascript, C, C++, C#, Java, Python Leetcode

Next
#37 Leetcode Sudoku Solver Solution in C, C++, Java, JavaScript, Python, C# Leetcode

Try With Live Editor

Category - Leetcode Online Judge Maniruzzaman Akash 1 year ago 833 1