Home » Technical Interview Questions » Matrix Interview Questions » Valid Sudoku

Valid Sudoku


Reading Time - 1 mins

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 Sudoku

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

Input Format

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

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.

READ  Sudoku Solver

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

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions