Valid Sudoku  

Difficulty Level Medium
Frequently asked in Amazon Apple Facebook Google Microsoft Oracle Pinterest Roblox Uber
Hash Hashing

Valid Sudoku is a problem in which we have given a 9*9  Sudoku board. We need to find the given Sudoku is valid or not on the basis of 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. Every of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Valid SudokuPin

Empty cells filled by ‘.’ in the input format.

Input Format  

Take input 9 lines where each line containing a string s of length 9.

Please click Like if you loved this article?

Output Format  

Print “YES” if partially filled sudoku is valid, else print “NO”.

Constraints  

  • s[i]=”.” or 1<=s[i]<=9.
Example Input:
8.6..3.9.
.4..1..68
2..87...5
1.8..5.2.
.3.1...5.
7.5.3.9..
.21..7.4.
6...2.8..
.876.4..3
Example Output:
YES

Explanation   

Check that there is any value that is repeated in a row, column, or 3*3 grid. If we found preparation print NO else print YES.

Algorithm  

Algorithm: 
Step:1 For each row check that their is repeatation of any digit present in filled cells.
Step:2 For each column check that their is repeatation of any digit present in filled cells.
Step:3 Check that every 3*3 grid must contain different values means no repeatation of any digit present in filled cells.
Step:4 Print "YES" if no repeatation of digit is found else print "NO".

Implementation For Valid Sudoku  

/*C++ Implementation of Valid Sudoku problem*/ 
#include<bits/stdc++.h>
using namespace std;
int main() 
{ 
    /*input suduko*/
    vector<string> v(10);
    for(int i=0;i<9;i++)
    {
        cin>>v[i];
    }
    /*use for store the count of digit 1-9*/
    int freq[10]={0};
    int flag=0;
    /*For each row check that their is repeatation of any digit present in filled cells.*/
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            /*for filled cells only*/
           if(v[i][j]!='.')
           {
               freq[v[i][j]-'0']++;
               /*if count is repeated*/
               if(freq[v[i][j]-'0']>1)
               {
                   flag=1;
                   goto label;
               }
           }
        }
        /*set all values to 0 for next time use*/
        memset(freq,0,sizeof(freq));
    }
    /*For each  chcolumneck that their is repeatation of any digit present in filled cells.*/
    for(int j=0;j<9;j++)
    {
        for(int i=0;i<9;i++)
        {
            /*for filled cells only*/
            if(v[i][j]!='.')
            {
               freq[v[i][j]-'0']++;
               /*if count is repeated*/
               if(freq[v[i][j]-'0']>1)
               {
                   flag=1;
                   goto label;
               }
            }
        }
        /*set all values to 0 for next time use*/
        memset(freq,0,sizeof(freq));
    }
    /*Check that every 3*3 grid must contain different values means no repeatation of any digit present in filled cells.*/
    for(int k1=0;k1<3;k1++)
    {
        for(int k2=0;k2<3;k2++)
        {
            for(int i=k1*3;i<k1*3+3;i++)
            {
                for(int j=k2*3;j<k2*3+3;j++)
                {
                    /*for filled cells only*/
                    if(v[i][j]!='.')
                    {
                        freq[v[i][j]-'0']++;
                        /*if count is repeated*/
                        if(freq[v[i][j]-'0']>1)
                        {
                            flag=1;
                            goto label;
                        }
                    }
                }
            } 
            /*set all values to 0 for next time use*/
            memset(freq,0,sizeof(freq));    
        }
    }
    label:;
    /*print "YES" if flag is 0 then sudoku is valid else "NO" valid*/
    if(flag==1)
    {
        cout<<"NO"<<endl;
    }
    else
    {
        cout<<"YES"<<endl;
    }    
    return 0; 
}
Input-1:
....5..1.
.4.3.....
.....3..1
8......2.
..2.7....
.15......
.....2...
.2.9.....
..4......
Output-1:
NO
Input-2:
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Output-2:
YES

Time Complexity  

O(9*9) Here we visit each cell of the sudoku 3 times and the total number of cells is 9*9 so, the time complexity is constant in this case.

See also
Count ways to reach the nth stair using step 1, 2 or 3

Space Complexity  

O(9*9) we use 9 strings of length 9, So here we need 9*9 space. If we don’t add the space for input as calculation then we say that time complexity is constant which is O(1). Simply implement by traversing the input values which means no extra space created or used.

References

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh