Q:

# Check for Valid Sudoku

Determine if a 9x9 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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Example:

<img src="https://www.includehelp.com/icp/Images/valid-sudoku.jpg" alt="Check for Valid Sudoku" max-width:="" 100%;"="" class="w3-border" style="box-sizing: border-box; border: 1px solid rgb(204, 204, 204) !important; margin-bottom: -5px;">

According to the above three rules - The 9X9 matrix is obviously a valid Sudoku

need an explanation for this answer? contact us directly to get an explanation for this answer

The above problem can be solved by checking all the three conditions which need to be satisfied for a Sudoku to be valid.

Pre-requisite:

Checking unique numbers in a set:

The above problem can be simply divided to sub-problems where in each sub-problem we simply need to check the numbers in the current set whether all are valid or not.

A current set can consist of numbers from a single row of the Sudoku, or from a single column, or from a 3X3 sub-box.

To check whether all numbers in the set are unique or not we can use set STL

```set<int> s;
For all numbers which are to be included in the set
IF s.find(number)==s.end()
It's a unique number and insert it into the set
ELSE
It's not a unique number
End For
```

Algorithm:

Divide the problem into three sub-problems

1. Check for each row consisting unique number
2. Check for each column consisting unique number
3. Check for each of 9 3X3 sub-boxes consisting unique number

For each sub-problem

1. Declare a set for each row/column/sub-box
2. Check whether the current row/column/sub-box have all unique no or not
3. If any row/column/sub-box fails to have all unique numbers, return false

If there is no such row/column/sub-box that returns false

Then it's a valid Sudoku & return true;

C++ implementation

``````#include <bits/stdc++.h>
using namespace std;

void print(vector<vector<char>> board){
//printing the sudoku
for(auto it=board.begin();it!=board.end();it++){
for(auto ij=(*it).begin();ij!=(*it).end();ij++){
printf("%c ",*ij);
}
printf("\n");
}
}

bool isValidSudoku(vector<vector<char>>& board) {
//checking for row
//check for unique numbers
for(auto it=board.begin();it!=board.end();it++){
set<char> s;
for(auto ij=(*it).begin();ij!=(*it).end();ij++){
if(*ij!='.'){
//finding unique numbers(represented as characters here)
if(s.find(*ij)==s.end()){
s.insert(*ij);
}
else
return false;
}
}
}
//checking for column
//check for unique numbers
for(int i=0;i<9;i++){//9X9 dimension
set<char> s;
for(int j=0;j<9;j++){
if(board[j][i]!='.'){
//finding unique numbers(represented as characters here)
if(s.find(board[j][i])==s.end()){
s.insert(board[j][i]);
}
else
return false;
}
}
}
//checking for sub-boxes
//check for unique numbers
for(int x=0;x<9;x=x+3){
for(int i=0;i<9;i=i+3){
set<char> s;
for(int j=x;j<x+3;j++){
for(int k=i;k<i+3;k++){
//finding unique numbers(represented as characters here)
if(board[j][k]!='.'){
if(s.find(board[j][k])==s.end()){
s.insert(board[j][k]);
}
else
return false;
}
}
}
}
}
return true;
}

int main(){
cout<<"black spaces represented as '.'\n";
vector<vector<char>> a{
{'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'}};

print(a);

if(isValidSudoku(a))
cout<<"It's a valid one"<<endl;
else
cout<<"It's a invalid sudoku\n";

vector<vector<char>> b{
{'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','.','.','9','9'}};

print(b);

if(isValidSudoku(b))
cout<<"It's a valid one"<<endl;
else
cout<<"It's a invalid sudoku\n";

return 0;
}
``````

Output

```black spaces represented as '.'
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
It's a valid one
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 . . 9 9
It's a invalid sudoku
```

Comment on outputs

For the first Sudoku, there is no violation of Sudoku rule for each row, each column, each of 9 3X3 sub-boxes. Thus it’s valid Sudoku.

For the second one there is two 9 in the last row, which violates the Sudoku rule. Thus it’s an invalid one.

need an explanation for this answer? contact us directly to get an explanation for this answer