36. 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:

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.

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

Intuition

Just check using BruteForce

Just that, 

For checking in sub-boxes
To divide in particular 

Use (row/3) * 3 + col /3
To find the respective index num, its just converting 2D to 1D

Links

https://leetcode.com/problems/valid-sudoku/description/

Video Links

Approach 1:

C++

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // Check for row
        for(int row=0; row<9; row++){
            unordered_set<char> checkrow;
            for(int col=0; col<9; col++){
                if(board[row][col] != '.' and checkrow.find(board[row][col]) != checkrow.end())
                    return false;

                checkrow.insert(board[row][col]);
            }
        }

        // Check for col
        for(int row=0; row<9; row++){
            unordered_set<char> checkcol;
            for(int col=0; col<9; col++){
                if(board[col][row] != '.' and checkcol.find(board[col][row]) != checkcol.end())
                    return false;

                checkcol.insert(board[col][row]);
            }
        }

        //Check for buckets
        vector<unordered_set<char>> buck(9); 
        for(int row=0; row<9; row++){
            for(int col=0; col<9; col++){
                int pos = (row/3)*3 + col/3;

                if(board[row][col] != '.' and buck[pos].find(board[row][col]) != buck[pos].end())
                    return false;

                buck[pos].insert(board[row][col]);
            }
        }

        return true;
    }
};

Approach 2:

Using Set , Short code

C++

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<set<int>> rows(9), cols(9), blocks(9);
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                
                if (board[i][j] == '.') continue;
                
                int curr = board[i][j] - '0';
                if (rows[i].count(curr) || cols[j].count(curr) || blocks[(i/3)*3+j/3].count(curr)) 
                    return false;
                
                rows[i].insert(curr);
                cols[j].insert(curr);
                blocks[(i/3)*3+j/3].insert(curr);
            }
        }
        
        return true;
    }
};

Approach 3:

C++

Approach 4:

C++

Similar Problems