In this article, we will discuss the Sudoku Solver problem with the help of various examples and explanations. The sudoku solver problem is considered a challenging problem and can be of two variations. One variation can be when we have been given unsolved sudoku, and we are required to solve it by filling the blank spaces with the correct number. The other variation is when we have been given unsolved sudoku, and we are supposed to check whether the given numbers are positioned correctly or not. We shall discuss the first variation in this article. The second variation can be found here:
Sudoku is a 9x9 puzzle where the board is divided into nine rows and nine columns. It is further divided into nine small grids of 3x3 size each. An element in sudoku is present exclusively in a row or a column, or a grid.
The input is a 9x9 vector of vectors of characters where '.' denotes a blank box. Wherever we encounter a dot, we are supposed to fill a number such that it is unique in its row, column and grid.
On solving the above sudoku, our output must be-
OUTPUT
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
For better visualization, the output will look like this:
Recommended: Try the Problem Yourself Before Moving onto the Solution
Approach
To solve the problem, we will be using the backtracking algorithm. We will traverse throughout the given sudoku and place a number that falls within the given constraints. If we cannot fill a number at a later stage, it means that we need to go back a few steps and make changes. How does this happen, you may ask? It is possible with the help of backtracking. We undo all the changes made up to the current cell, backtrack to the cell causing the problem, and then start again. We do this until we reach the desired solution. To carry out all the operations successfully, we will be performing the following steps:
We first create a map that stores in which grid we are and which element are we looking for. For example,
map <pair<int,int>, map<int,int>> mp;
This statement creates a map variable named mp. The first part stores the sudoku grid, like (0,0) or (0,1) and so on. The second part stores the number in the cell of the sudoku.
We also create two vectors to store the values of rows and columns.
We then populate our map by using two for loops and checking for '.'. If there is a dot in a cell, we don’t do anything. We change the value at the grid, row, and column to 1 (true). This shows that a particular value at (i,j) in the sudoku board is present in the map at the (i/3, j/3) grid.
After populating our map and two vectors, we call our recursive function to fill our map and solve the sudoku.
The name of our recursive function is helper(). It takes six arguments- the row number, the column number, the input board, the map, the row vector, and the column vector.
It should be noted that we are using pass-by-reference to pass the function arguments. This helps us reduce our space usage drastically.
The base case of our recursive function is when the row counter reaches 9. This means that we have successfully traversed the whole sudoku board and filled all the values, and we cannot move any further as a sudoku board has only nine rows (0 to 8) and nine columns (0 to 8). So at this stage, we just print our sudoku board.
In the next condition, we check when the column counter value is 9. This means that the whole column has been traversed, and we have to go to the next row.
Since we cannot change the already filled cells, we check for such cases and simply move ahead.
Now comes the main part of our program, where we fill the whole map and both the vectors. We make a for loop starting from 1 up to 9 (the possible numbers that can be placed in our sudoku). Then, for each i, we check if it is present in a particular grid, row, or column. To find out the grid coordinate, we maintain two variables-
block_row, which is equal to row/3.
block_column, which is equal to column/3.
These two values help us find the grid. The grid numbering starts from (0,0) in the top left and goes up to (2,2) in the bottom right.
If a value is not present in a grid, row, or column, we add it to our board and make the corresponding value true in our map, row vector, and column vector. Since our input board is a vector of vectors of characters, we add '0' to the number to convert the number into a character.
After adding the value to our board, we proceed to the next column by calling the recursive function at (col+1).
In the solution code provided, we have four extra lines written after the recursive function calling. They are-
mp[{block_row, block_col}][i] = 0;
rows[row][i] = 0;
cols[col][i] = 0;
board[row][col] = '.';
These four lines help us in backtracking. Why do we write it, you may ask? The answer to this is simple. Once a value has been added to our sudoku board, we are not 100% sure that the value inserted by us is correct. At the time of filling that element, it might fulfill all our conditions, but a time may come at a later stage when we are unable to fill our sudoku with an appropriate number. In such cases, we undo all the changes made up until that cell by changing the values in our map and row and column vector to 0 (false). We also undo the change made to our board. These four lines are the most important as they ensure we can fill our sudoku board.
You may be a bit confused after reading the approach. But don’t worry, simplified pseudocode is provided below.
Pseudocode
Start from (0,0) and traverse up to (8,8).
Try all the possible valid combinations.
If (number already present), then move forward.
Else
for(numbers= 1 to 9)
If we can place the number at (x,y), then place the number at (x,y) and move forward.
It is highly recommended to write your pseudocode and a partial code before moving to the solution code.
If you are confident enough and want to try out your implement somewhere, don’t worry. You can try the question first on our Coding Ninjas Studio by clicking here, Sudoku Solver.
C++ Implementation of Sudoku Solver
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
using namespace std;
void helper(int row, int col, vector<vector<char>> &board, map<pair<int, int>, map<int, int>> &mp, vector<map<int, int>> &rows, vector<map<int, int>> &cols){ //using pass by reference to save storage space
//base case
if(row == 9){
for(auto it : board){
for(auto i : it){
cout << i << " ";
}
cout << "\n" ;
}
cout << "\n" ;
return ;
}
if(col == 9){ //means we have filled the whole column and we want to go to the next row
helper(row+1, 0, board, mp, rows, cols);
return ;
}
if(board[row][col] != '.'){
//not empty case
helper(row, col+1, board, mp, rows, cols);
return ;
}
for(int i=1; i<=9; i++){
int block_row = row/3, block_col = col/3;
if(! mp[ {block_row, block_col} ][i] && !rows[row][i] && !cols[col][i]){
mp[{block_row, block_col}][i] = 1;
rows[row][i] = 1;
cols[col][i] = 1;
board[row][col] = i + '0';
helper(row, col+1, board, mp, rows, cols);
//undo all the changes for backtracking
mp[{block_row, block_col}][i] = 0;
rows[row][i] = 0;
cols[col][i] = 0;
board[row][col] = '.';
}
}
}
void solveSudoku(vector<vector<char>> &board){
map<pair<int, int>, map<int, int>> mp;
vector<map<int, int>> rows(9); //particular row
vector<map<int, int>> cols(9); //particular column
//populating our map according to the input
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
if(board[i][j] != '.'){
mp[{i/3, j/3}][board[i][j] - '0'] = 1;
rows[i][board[i][j] - '0'] = 1;
cols[j][board[i][j] - '0'] = 1;
}
}
}
helper(0, 0, board, mp, rows, cols);
}
int main(){
vector<vector<char>> board = {
{'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'}
};
solveSudoku(board);
}
You can also try this code with Online C++ Compiler
In the code mentioned above, we traverse the whole sudoku board and fill all the empty cells. Thus the time complexity is, T(n) = O(9(n*n)) where n is the number of empty cells to be filled
Space Complexity
In the given code, we create a n*n vector to store our sudoku board. Various changes and updates are made to it. Thus, Space complexity = O(n*n), where n is the size of the input vector.
What are the various techniques to solve the Sudoku Solver problem?
One of the techniques used to solve the sudoku solver is given in this article. A few other techniques are-
Eliminating squares using Naked Pairs in a grid.
Eliminating squares using Naked Pairs in rows and columns.
Eliminating squares using Hidden Pairs in rows and columns.
Conclusion
To summarize the article, we had an in-depth discussion on the Sudoku Solver problem. We first learned why we should study this problem. After seeing the problem statement and an example, we came up with an approach using backtracking and saw a code for the same.
8+ registered 