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