# 36. Valid Sudoku

Determine if a 9x9 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 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.

# Solution

Approach 1: Verify each row, column, and sub-box.

# Code (Python)

Approach 1:

    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # idea: number the rows, cols, boxes from 1-9. Go through each number on the board, mark its presence.
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    continue
                if (board[i][j] in rows[i]) or (board[i][j] in cols[j]) or (board[i][j] in boxes[(i//3) * 3 + j//3]):
                    return False
                rows[i].add(board[i][j])
                cols[j].add(board[i][j])
                boxes[(i//3) * 3 + j//3].add(board[i][j])
        return True

    #######################
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        for row in board:
            if not self._verify((num for num in row)):
                return False
        for col in range(len(board[0])):
            if not self._verify((board[i][col] for i in range(len(board)))):
                return False
        offsets = ((0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2))
        for i in range(3):
            for j in range(3):
                if not self._verify((board[3*i+offset[0]][3*j+offset[1]] for offset in offsets)):
                    return False
        return True
    
    def _verify(self, stuff):
        seen = set([])
        for item in stuff:
            if item == '.':
                continue
            if item in seen:
                return False
            seen.add(item)
        return True

# Code (C++)

Approach 1:

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool rowVisited[9][9] = {false};
        bool colVisited[9][9] = {false};
        bool boxVisited[9][9] = {false};
        for (int i = 0; i < board.size(); ++i)
        {
            for (int j = 0; j < board[0].size(); ++j)
            {
                if (board[i][j] == '.')
                    continue;
                int digit = board[i][j] - '1';
                int k = i / 3 * 3 + j / 3;
                if (rowVisited[i][digit] || colVisited[j][digit] || boxVisited[k][digit])
                    return false;
                rowVisited[i][digit] = true;
                colVisited[j][digit] = true;
                boxVisited[k][digit] = true;
            }
        }
        return true;
    }
};