C++ Simple Solution + Detailed Explanation


#1

We have to do 3 types of traversals to validate our Sudoku.

  1. Each Row
  2. Each Column
  3. Each 3X3 Grid.

Its simple to do Row traversals and Column traversals, since its easy to differentiate two rows by their indexes (same for columns).

So first lets find a factor that differentiates each 3X3 sector/grid.
Its by simple observation, the factor comes as
grid-factor = (colIndex/3)+10*(rowIndex/3);

So since we have to check each row for duplicates, the best is to use set for that. And also since we are checking it for every index, we use a map.

unordered_map<int, unordered_set<char>> row, col, grid;

Now while traversing we first check if the character is a digit or not. Then search for its duplicate in the respective set.

  1. For Row/ Column.
    if(row[i].find(A[i][j]) != row[i].end() || col[j].find(A[i][j]) != col[j].end()) return 0;

  2. For each 3X3 grid

int sec = (j/3)+10*(i/3);
if(grid[sec].find(A[i][j]) != grid[sec].end()) return 0;

  1. If not found in either of them, we simply insert into the set
    row[i].insert(A[i][j]);
    col[j].insert(A[i][j]);
    grid[sec].insert(A[i][j]);

Hence, the full code!

int Solution::isValidSudoku(const vector<string> &A) {
    unordered_map<int, unordered_set<char>> row, col, grid;
    for(int i=0; i<A.size(); i++){
        for(int j=0; j<A[i].length(); j++){
            if(isdigit(A[i][j])){
                if(row[i].find(A[i][j]) != row[i].end() || col[j].find(A[i][j]) != col[j].end())
                    return 0;
                int sec = (j/3)+10*(i/3);
                if(grid[sec].find(A[i][j]) != grid[sec].end())
                    return 0;
                row[i].insert(A[i][j]);
                col[j].insert(A[i][j]);
                grid[sec].insert(A[i][j]);
            }
        }
    }
    return 1;
}