Notes

36. Valid Sudoku

4 min read

Prompt

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

Examples

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

Solutions

Basic Solution

In C++

    bool isValidSudoku(vector<vector<char>>& board) {
        for (const auto& row : board) {
            bool freq[9] = {}; 
            for (char e : row) {
                if (e == '.') continue;
                size_t i = e - '1';
                if (freq[i]) return false;
                freq[i] = true;
            }
        }
        for (int bx = 0; bx < 9; ++bx) {
            bool freq[9] = {}; 
            for (int y = 0; y < 9; ++y) {
                char e = board[y][bx];
                if (e == '.') continue;
                size_t i = e - '1';
                if (freq[i]) return false;
                freq[i] = true;
            }
        }
        for (int by = 0; by < 3; ++by) {
            for (int bx = 0; bx < 3; ++bx) {
                bool freq[9] = {}; 
                for (int y = 0; y < 3; ++y) {
                    for (int x = 0; x < 3; ++x) {
                        char e = board[by * 3 + y][bx * 3 + x];
                        if (e == '.') continue;
                        size_t i = e - '1';
                        if (freq[i]) return false;
                        freq[i] = true;
                    }
                }
            }
        }
        return true;
    }

Explanation

Foreach row, col, block, verify the required conditions.

Big O Analysis

Time Complexity

The time complexity is . Worse than the others because is is

Auxiliary Space Complexity

The space complexity is

Set Solution

In C++

bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<int> set;
        for (size_t row = 0; row < 9; ++row) {
            for (size_t col = 0; col < 9; ++col) {
                char e = board[row][col];
                if (e == '.') continue;
                int block = (row / 3) * 3 + (col / 3);
                int num = e - '0';
                int rv = (row + 1) * 10 + num;
                int cv = (col + 1) * 100 + num;
                int bv = (block + 1) * 1000 + num;
                if (set.contains(rv)) return false;
                if (set.contains(cv)) return false;
                if (set.contains(bv)) return false;
                set.insert(rv);
                set.insert(cv);
                set.insert(bv);
            }
        }
        return true;
    }

Explanation

The idea is, we add each number to a set, with a tag based on its row, column, or block. If we ever try to add a tagged number to the set that is already in it, that means the sudoku is invalid.

Big O Analysis

Time Complexity

The time complexity is , specifically .

Auxiliary Space Complexity

The space complexity is due to the set.

Bitmask Solution

In C++

    bool isValidSudoku(vector<vector<char>>& board) {
        int row_bm[9] = {};
        int col_bm[9] = {};
        int block_bm[9] = {};
 
        for (size_t row = 0; row < 9; ++row) {
            for (size_t col = 0; col < 9; ++col) {
                char e = board[row][col];
                if (e == '.') continue;
                int block = (row / 3) * 3 + (col / 3);
                int shift = e - '1';
                int m = 1 << shift;
 
                if ((row_bm[row] & m) != 0) return false;
                if ((col_bm[col] & m) != 0) return false;
                if ((block_bm[block] & m) != 0) return false;
                
                row_bm[row] |= m;
                col_bm[col] |= m;
                block_bm[block] |= m;
            }
        }
        return true;
    }

Explanation

Actually very similar to the Basic Solution, but we are able to adapt it to only process each cell once, by storing all of the different bitmasks at the top of the function, and then accessing and setting them within the loop. It is otherwise the exact same logic as before.

Big O Analysis

Time Complexity

The time complexity is , specifically

Auxiliary Space Complexity

The space complexity is

Graph View