Valid Sudoku

---

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

---

Try this Problem on your own or check similar problems:

1. Check if Every Row and Column Contains All Numbers
2. Sudoku Solver

Solution:

Java

class Solution {
  public boolean isValidSudoku(char[][] board) {
      for(int i = 0; i < board.length; ++i){
          for(int j = 0; j < board.length; ++j){
              if(board[i][j] != '.' && !isValidCell(board, i, j, board[i][j])) return false;
          }
      }

      return true;
  }


  private boolean isValidCell(char[][] board, int row, int column, char value){
    for(int i = 0; i < 9; ++i){
      if(i == row || i == column) continue;
      if(board[i][column] == value || board[row][i] == value) return false;
    }

    int rowGroup = row / 3, columnGroup = column / 3;
    for(int i = 0; i < 3; ++i){
      for(int j = 0; j < 3; ++j){
          int r = i + rowGroup * 3, c = j + columnGroup * 3;
          if(r == row && c == column) continue;
          if(board[r][c] == value) return false;
      }
    }

    return true;
  }
}

JavaScript

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function (board) {
  for (let i = 0; i < board.length; ++i) {
    for (let j = 0; j < board.length; ++j) {
      if (board[i][j] !== "." && !isValidCell(board, i, j, board[i][j])) {
        return false;
      }
    }
  }

  return true;
};
function isValidCell(board, row, column, value) {
  for (let i = 0; i < 9; ++i) {
    if (i === row || i === column) continue;
    if (board[i][column] === value || board[row][i] === value) return false;
  }

  const rowGroup = Math.floor(row / 3);
  const columnGroup = Math.floor(column / 3);
  for (let i = 0; i < 3; ++i) {
    for (let j = 0; j < 3; ++j) {
      const r = i + rowGroup * 3;
      const c = j + columnGroup * 3;
      if (r === row && c === column) continue;
      if (board[r][c] === value) return false;
    }
  }

  return true;
}

Python

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
      def isValidCell(board, row, column, value):
        for i in range(9):
            if i == row or i == column:
                continue
            if board[i][column] == value or board[row][i] == value:
                return False

        rowGroup = row // 3
        columnGroup = column // 3
        for i in range(3):
            for j in range(3):
                r = i + rowGroup * 3
                c = j + columnGroup * 3
                if r == row and c == column:
                    continue
                if board[r][c] == value:
                    return False
        return True

      for i in range(len(board)):
        for j in range(len(board)):
            if board[i][j] != '.' and not isValidCell(board, i, j, board[i][j]):
                return False
      return True

C++

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
      for (int i = 0; i < board.size(); ++i) {
          for (int j = 0; j < board.size(); ++j) {
              if (board[i][j] != '.' && !isValidCell(board, i, j, board[i][j])) {
                  return false;
              }
          }
      }
      return true;
    }

    bool isValidCell(vector<vector<char>>& board, int row, int column, char value) {
        for (int i = 0; i < 9; ++i) {
            if (i == row || i == column) continue;
            if (board[i][column] == value || board[row][i] == value) return false;
        }

        int rowGroup = row / 3;
        int columnGroup = column / 3;
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                int r = i + rowGroup * 3;
                int c = j + columnGroup * 3;
                if (r == row && c == column) continue;
                if (board[r][c] == value) return false;
            }
        }

        return true;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(1)
• Space Complexity: O(1)

---

Explanation:

Both space and time complexity are constant since we're dealing with limited size board 9x9. For each cell we call isValidCell which checks if for any other cell in the same row, same column or same submatrix 3x3 is of the same value, while also making sure we don't compare the current cell with itself. To get the right submatrix we use rowGroup = row / 3, columnGroup = column / 3, and for creating right position for indices we use r = i + rowGroup * 3, c = j + columnGroup * 3. This sudoku validation is used for solving the sudoku in Sudoku Solver.