The greatest effort is not connected with results.
~Atisha
Sudoku Solver
Welcome Back Reader!
We hope that you are doing great with Recursion so far. In this article we will discuss about the next problem
based on Recursion and Backtracking i.e. Sudoku Solver.
You might have solved a Sudoku puzzle in a newspaper or on mobile and therefore you might also know the rules
of the games too. In this problem we will build a program which can solve any Sudoku puzzle in a fraction of
seconds. Sounds Interesting? Right!
Before you move any further, it is advised that you give this problem a fair try.
Lets jump to the problem.
Understanding the problem:
In this problem you are given a partially filled 9*9 2-D array(arr) which represents an incomplete Sudoku
state.
All you are required to do is assign the digits from 1 to 9 to the empty cells following some rules.
Rule 1 -> Digits from 1-9 must occur exactly once in each row.
Rule 2 -> Digits from 1-9 must occur exactly once in each column.
Rule 3 -> Digits from 1-9 must occur exactly once in each 3x3 sub-array of the given 2D array.
Assumption -> The given Sudoku puzzle will have a single unique solution.
Just by following the rules of the games, you can achieve this output.
For more clarity of the question, watch part of the video.
Approach:
Let us go through the rules again:
Each row should have a number from 1 to 9 without repetition.
Each row should have a number from 1 to 9 without repetition.
Each 3 X 3 box should have a number from 1 to 9 without repetition.
Sudoku can be divided into 9, 3 X 3 boxes as shown in the image below.
With the help of recursion and backtracking, we will try to place every number from 1 to 9 on the cell
where zero is present.
But before using that number, we will first check whether that number is valid or not by checking whether
the current row, column or sub matrix contains the number already.
And if that number is already present we will not place it.
If it is not present, we will place the number on the current cell (mark) and move to the next cell which
has zero.
If we have tried all the numbers and we still do not find any valid number, we will use backtracking and
unmark all the cells that we marked before and repeat the process for a new number.
If we reach the end of the Sudoku, it means that we have found a valid Sudoku, and we will print it.
For more clarity of this part, watch part of the video.
Lets try to code this!
Signature: public static void solveSudoku(int[][] board, int i, int j)
Board - given 9 X 9 Sudoku board.
i -> Current row index
j -> Current column index
public static void solveSudoku(int[][] board, int i, int j) {
if (i == board.length){
display(board);
return;
}
int ni = 0;
int nj = 0;
if(j == board[0].length - 1){
ni = i + 1;
nj = 0;
} else {
ni = i;
nj = j + 1;
}
if(board[i][j] != 0){
solveSudoku(board, ni, nj);
} else {
for(int val = 1; val <= 9; val++){ if(isValid(board, i, j, val)){ board[i][j]=val; solveSudoku(board, ni, nj);
board[i][j]=0; } } } }
java;
true";
From the main function we will call solveSudoku, passing the board and 0, 0 for i and j.
First we will make the new i, j from the current i, j. We will check if j is at the end of the current
row (j == 8). If it is ni = i + 1 and nj = 0. Else, nj = j +1 and ni = i.
If the board[i][j] == 0, then we will try to put every number from 1 to 9 in that cell, else we will
just call the recursive function for the ni and nj.
To check whether the number is a valid option or not, we will create another function, isValid
to which we will pass board, current row index, current column index and the number for which we are
checking.
For more clarity of this code, watch part of the video.
Signature: public boolean void isValid(int[][] board, int x, int y, int val)
Board - given 9 X 9 Sudoku board.
x -> Current row index
y -> Current column index
public static boolean isValid(int[][] board, int x, int y, int val) {
int n = board.length;
for (int i = 0; i < n; i++) { if (board[x][i]==val) { return false; } } for (int i=0; i < n; i++) { if
(board[i][y]==val) { return false; } } x=x / 3 * 3; y=y / 3 * 3; for (int i=0; i < 3; i++) { for (int
j=0; j < 3; j++) { if (board[x + i][y + j]==val) { return false; } } } return true; }
java;
true";
Row Check:
We will use a for loop on the current row, by changing the column index and checking whether the value
is present on that row. If it is, return false as this number is already present on the current row.
Column Check:
We will use a for loop on the current column, by changing the row index and checking whether the value
is present on that column. If it is, return false as this number is already present on the current
column.
Box Check:
Board can be divided into 9 3 X 3 submatrices.
For every submatrix , the cell marked as * is common. If we somehow reach the cell marked as * from
the respective submatrix, then with the help of two for loops we can search that respective submatrix.
To get the index of the top leftmost point for the submatrix we use the relation: x = x / 3 * 3 y = y / 3 * 3
For example if x = 8 and y = 1, then the index of the * cell will be (6 , 0)
By relation we get: x = 8 /3 * 3, x = 6 y = 1 /3 * 3, y = 0
Now with the help of two for loops we will search whether the value is present in that submatrix or
not.
Code flow: We will start from 0,0 cells. If that cell is zero, we will check which all numbers
from 1 to 9 can be placed. If isValid returns true, then we will place that number there, we will mark
the current cell by placing that number in that cell. If after certain steps, we find that no number can
be placed, we will backtrack and unmark all the cells that we marked and place a new number.
In pre - order we will mark the cell, in post - order we will unmark the cell.
Base Case: If the row index is equal to the 9, it means we have filled the board (we are out of
the board). We will print it and return.
For more clarity of the isValid function, watch part of the video.
Complexities:
Time Complexity: O(9^(n*n))
At each blank there are 9 possible options to explore. And at max there can be (n*n) blanks; so the
average/upper bound time complexity becomes O(9^(n*n)).
Space Complexity: O(1)
Only a 2D array of dimensions (9*9) has been used initially, but no extra space has been used by the
recursion function therefore making the space complexity O(1)/constant.
Complete Code:
import java.io.*;
import java.util.*;
public class Main {
public static void display(int[][] board){
for(int i = 0; i < board.length; i++){ for(int j=0; j < board[0].length; j++){
System.out.print(board[i][j] + " " ); } System.out.println(); } } public static void solveSudoku(int[][]
board, int i, int j) { if (i==board.length){ display(board); return; } int ni=0; int nj=0;
if(j==board[0].length - 1){ ni=i + 1; nj=0; } else { ni=i; nj=j + 1; } if(board[i][j] !=0){
solveSudoku(board, ni, nj); } else { for(int val=1; val <=9; val++){ if(isValid(board, i, j, val)){
board[i][j]=val; solveSudoku(board, ni, nj); board[i][j]=0; } } } } public static boolean
isValid(int[][] board, int x, int y, int val) { int n=board.length; for (int i=0; i < n; i++) { if
(board[x][i]==val) { return false; } } for (int i=0; i < n; i++) { if (board[i][y]==val) { return false;
} } x=x / 3 * 3; y=y / 3 * 3; for (int i=0; i < 3; i++) { for (int j=0; j < 3; j++) { if (board[x + i][y
+ j]==val) { return false; } } } return true; } public static void main(String[] args) throws Exception
{ Scanner scn=new Scanner(System.in); int[][] arr=new int[9][9]; for (int i=0; i < 9; i++) { for (int
j=0; j < 9; j++) { arr[i][j]=scn.nextInt(); } } solveSudoku(arr, 0, 0); } }
java;
true";
We hope that this article was helpful. If somehow you are finding it difficult to understand this
problem then we advise you to watch our video lecture of this problem.
Trust me it will just get easier to understand after you have watched the solution video.
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem.
All the best for an exciting future!
Happy Coding!
