Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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

Author 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'}
}

 

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

 

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

 

 

 

 

 

 

 

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
    // No answer exist
    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!

 

Previous article
Arrange Elements of Given Array in a Mathematical Expression using Operators [+, -, *, /] and Parentheses to Get Value 28
Next article
Permutations of a Given Number That are Powers of 2
Live masterclass