1.
Introduction
2.
Problem statement
3.
Approach
4.
Code
5.
Complexity analysis
6.
FAQs
7.
Key Takeaways
Last Updated: Mar 27, 2024

# Solve Sudoku on the Basis of the Given Irregular Regions

Malay Gain
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

## Introduction

Sudoku is one of the popular combinatorial and logic-based number-placement puzzles. We are mostly familiar with 9Ă—9 grid-based puzzles where each row and column and each 3Ă—3 subgrids should contain all of the numbers from 1 to 9. Here, we will see a special type of sudoku with irregular sub-regions inside the grid and the grid can be of any given nĂ—n size. Here we need to fill each column and row as well as subregions so that it contains contain all of the numbers from 1 to n.

Recommended topic about, kth largest element in an array, and Euclid GCD Algorithm

## Problem statement

You are given nĂ—n sudoku puzzle grid and region[ ][ ] matrix denoting irregular sub-regions inside the puzzle grid with characters. The same characters denote a specific sub-region.

Your task is to fill empty cells of the puzzle grid with numbers from 1 to n so that the below conditions are satisfied.

• Each row and column should contain all of the numbers from 1 to n.
• Each subregion also should contain all of the numbers from 1 to n.

Note: empty cells will be denoted by 0.

Input

``````int n= 7
sudoku[ ][ ]
= {
{0, 0, 0, 0, 0, 0, 0},
{0, 0, 2, 0, 4, 0, 0},
{3, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 5, 0, 2},
{5, 0, 0, 0, 0, 0, 3},
{0, 0, 1, 0, 0, 0, 5},
{2, 0, 0, 0, 0, 0, 1}
}
region[ ][ ]
={
{'r', 'r', 'r', 'b', 'b', 'b', 'b'},
{'g', 'r', 'r', 'r', 'r', 'b', 'o'},
{'g', 'g', 'g', 'g', 'b', 'b', 'o'},
{'p', 'p', 'g', 'o', 'o', 'o', 'o'},
{'p', 'p', 'g', 'd', 'o', 'l', 'l'},
{'p', 'p', 'p', 'd', 'l', 'l', 'l'},
{'d', 'd', 'd', 'd', 'd', 'l', 'l'}
}``````

Output

Explanation

Letâ€™s consider an unfilled cell of the grid, say (0,0). We will try to fill it with every possible number from 1 to 7. If any number is present neither in its current row, column nor in the current subregion, we will fill the cell with that number and will go to the next cell (0,1) and repeat the same process. In this way, if at any cell the conditions are mismatched, we will backtrack and try to fill the cells with other possibilities. If all cells are filled, then the puzzle is solved.

But If all cells are not filled after considering all possibilities, then the sudoku canâ€™t be solved.

Note: Please try to solve the problem first and then see the below solution approach.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Approach

Here we will take the backtracking approach to solve the sudoku puzzle.

• Recursively visit each cell of the puzzle grid.
• If the current cell is filled with any number from 1 to n, then move to the next cell.
• Otherwise, if the cell is not filled yet, check with all possible numbers from 1 to n.
• For checking which number is satisfying all given conditions, we will define a function check(i,j, num) that will first check if num[1,n] is already present in the current row(ith) or not.

If present then return false as num violates the row condition.

Otherwise, check if num[1,n] is already present in the current column(jth) or not.

If present then return false as num violates the column condition.

Otherwise, check if num[1,n] is already present in the current sub-region or not.

For visiting every cell of the current subregion, we will use the BFS algorithm.

If none of the cells of the subregion is having the same number as num, then return true, otherwise false.

• If the current cell is filled, then recursively move to the next cell. Otherwise backtrack from the current cell.

## Code

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

bool check(int i,int j,int num,int n,vector<vector<int>> sudoku,vector<vector<char>> region)
{
//check row
for(int k=0;k<n;k++)
{
if(sudoku[i][k]==num) return false;
}

//check for column
for(int k=0;k<n;k++)
{
if(sudoku[k][j]==num) return false;
}

//check the subregion, (i,j) cell part of

//using BFS ,check if num is safe for the cell
char c=region[i][j];

//storing if a cell is visited(1) or not(0)
int vis[n][n];
memset(vis,0,sizeof(vis));

queue<pair<int,int>> q;

q.push(make_pair(i,j));

//(i,j) visited
vis[i][j]=1;

while(!q.empty())
{
pair<int,int> f=q.front();

q.pop();
//iterate over four negihbours f cell

//first neighbour
if(f.second-1>=0 && region[f.first][f.second-1]==c && !vis[f.first][f.second-1])
{
//sub-region already having the number 'num'
if(sudoku[f.first][f.second-1]==num)
{
return false;
}
q.push(make_pair(f.first,f.second-1));

//mark the neighbour as visited
vis[f.first][f.second-1]=1;

}

//second neighbour
if(f.second+1<n && region[f.first][f.second+1]==c && !vis[f.first][f.second+1])
{
//sub-region already having the number 'num'
if(sudoku[f.first][f.second+1]==num)
{
return false;
}
q.push(make_pair(f.first,f.second+1));

//mark the neighbour as visited
vis[f.first][f.second-1]=1;

}

//third neighbour
if(f.first-1>=0 && region[f.first-1][f.second]==c && !vis[f.first-1][f.second])
{
//sub-region already having the number 'num'
if(sudoku[f.first-1][f.second]==num)
{
return false;
}
q.push(make_pair(f.first-1,f.second));

//mark the neighbour as visited
vis[f.first-1][f.second]=1;

}

//fourth neighbour
if(f.first+1>=0 && region[f.first+1][f.second]==c && !vis[f.first+1][f.second])
{
//sub-region already having the number 'num'
if(sudoku[f.first+1][f.second]==num)
{
return false;
}
q.push(make_pair(f.first,f.second-1));

//mark the neighbour as visited
vis[f.first+1][f.second]=1;

}

}

return true;

}

bool sudokuSolver(int i,int j,int n,vector<vector<int>> &sudoku,vector<vector<char>> &region)
{

//check for (i,j) cell by filling it with every number from 1 to n
// and store the number that stisfies all given conditions;
// then recursively move to next cell
if(i==n)
{
for (int a = 0; a < n; a++) {
for (int b = 0; b < n; b++) {
cout << sudoku[a][b] << " ";
}
cout << endl;
}
return true;
}

if(j==n)
{
//recusive call next row
return sudokuSolver(i+1,0,n,sudoku,region);
}

//if current cell is filled move to next cell
if(sudoku[i][j]!=0)
{
return sudokuSolver(i,j+1,n,sudoku,region);
}
else
{
for(int k=1;k<=n;k++)
{
if(check(i,j,k,n,sudoku,region))
{
sudoku[i][j]=n;

if(sudokuSolver(i,j+1,n,sudoku,region))
{
return true;
}
}
}

sudoku[i][j]=0;
return false;
}

}

//driver code

int main()
{
int N=2;
// Given sudoku array
vector<vector<int>> sudoku {
{ 0, 1 },
{ 0, 0 }
};

// Given region array
vector<vector<char>> region {
{ 'r', 'r' },
{ 'b', 'b' }
};

// Function call
if (sudokuSolver( 0, 0, N,sudoku, region)) {
cout<<"solved"<<endl;
}
else {
cout << "-1";
}
return 0;
}
``````

Output

``````6 1 3 4 2 5 7
1 7 2 5 4 3 6
3 5 7 2 1 6 4
7 6 4 3 5 1 2
5 2 6 1 7 4 3
4 3 1 7 6 2 5
2 4 5 6 3 7 1
solved``````

## Complexity analysis

As there are n possible options for every unfilled cell in the sudoku grid and there are in total n2 number of cells in the grid. So, the time complexity is O( ), and space complexity is O(n2).

## FAQs

1. What is backtracking?
The Backtracking algorithm refers to searching and going through every possible combination in order to solve a particular computing problem. Broadly classifying, the backtracking algorithm can be divided into 3 further categories. These include searching for all feasible solutions, searching for the best solution, and searching for any feasible solution.

2. Why the vector in C++ called dynamic array?
Vector can resize itself when an element is inserted or deleted from the vector.

## Key Takeaways

This article covered how to solve the sudoku puzzle on the basis of the given irregular regions.

Check out the Coding Ninjas Studio library for getting a better hold of the backtracking algorithm.

Side by side, you can also go through another article on sudoku puzzle and practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here.

Happy learning!

Live masterclass