# Valid Sudoku  Difficulty Level Medium
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. 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={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.

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 