Solve Sudoku on the Basis of the Given Irregular Regions

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;
}

You can also try this code with Online C++ Compiler

Run Code

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

You can also try this code with Online C++ Compiler

Run Code

Complexity analysis

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

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!