Home » Interview coding problems/challenges

Check for Valid Sudoku

In this article, we are going to see how to check for a valid Sudoku in C++? This can be featured as functional problem in interview coding rounds. Submitted by Radib Kar, on January 08, 2019

Problem statement

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:

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

Solution:

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.