You are give a partially filled 9*9 2-D array (arr) which represents an
incomplete sudoku state.
You are required to 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.
0 represents an empty cell.
We assume that the given Sudoku puzzle will have a single unique solution.
Let the input array of incomplete Sudoku look like as shown in figure 1.
figure 1
It is highly recommended to first understand the solution using recursion as this
solution will highly rely on the recursive solution.
APPROACH
To abide by the Sudoku number placing rules we will make use of bit
manipulation.
Here, we will be maintaining a row array and a column array of size N which
at any instant will store the numbers already present in that particular row or
column.
Figure 2
We assume that the given Sudoku puzzle will have a single unique solution.
We will represent the number 1 to N in the form of bits by setting the bit at
the corresponding position.
Also, we will be maintaining a sub-matrix array of size N1/2 * N1/2 which will
be storing the numbers that are already filled up in the sub matrix.
So now instead of checking for every number by searching in the entire row,
column and sub-matrix by iterating here we can just check for respective bit
value.
This henceforth makes our code efficient but at the cost of space as we are
creating three arrays.
The rest implementation is similar to that of a recursive solution.
Reader, if you have gone through the above approach and the solution video of
"Sudoku using Recursion", then you will find its code quite simple.
Have a look at it.
import java.io.*;
import java.util.*;
public class Main {.
public static void display(int[][] arr){
for (int ii = 0; ii < arr.length; ii++) {
for (int jj = 0; jj < arr.length; jj++) {
System.out.print(arr[ii][jj] + " ");
}
System.out.println();
}
System.out.println();
}
public static void solveSudoku(int[][] arr, int[] rows, int[] cols, int[][] gri
d, int i, int j) {
if(i==arr.length){ //1
display(arr);
return;
}
if(arr[i][j]>0){ //2
solveSudoku(arr,rows,cols,grid,j==arr.length-1?i+1:i, j==arr[0].length-
1?0:j+1);
}else{ //3
for(int num=1;num<=9;num++){
if((rows[i]&(1<<num))==0 && (cols[j]&(1<<num))==0 && (grid[i/3][j/3]&
(1<<num))==0){
arr[i][j]=num; //4
rows[i]^=(1<<num);
cols[j]^=(1<<num);
grid[i/3][j/3]^=(1<<num);
solveSudoku(arr,rows,cols,grid,j==arr.length-1 ? i+1 :i,
j==arr[0].length-1 ? 0:j+1); //5
grid[i/3][j/3]^=(1<<num); //6
cols[j]^=(1<<num);
rows[i]^=(1<<num);
arr[i][j]=0;
}
}
}
}
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int[][] arr = new int[9][9];
int[] rows = new int[9];
int[] cols = new int[9];
int[][] grid = new int[3][3];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
int digit = scn.nextInt();
arr[i][j] = digit;
rows[i] |= (1 << digit);
cols[j] |= (1 << digit);
grid[i / 3][j / 3] |= (1 << digit);
}
}
solveSudoku(arr, rows, cols, grid, 0, 0);
}
}
java;
true";
If we have reached beyond the last row, then we print the completed sudoku
array and return from the function.
If the cell is already filled then we can't make any changes to that cell.
We make a recursive call to the function.
If we reach the last column, then we move on to the next row and the first column.
Else the row remains the same and we simply move to the next column.
If the cell is empty i.e. 0, then we run the loop from the numbers 1 to 9.
We need to check that the bit corresponding to the num is OFF (or 0) in the row
array, the column array and the grid by toggling.
Now, we first assign the cell with the current "num". Next we switch ON the
corresponding bit in "rows", "cols" and "grid".
We call the recursion function to move to the next cell as shown in.
When backtracking from recursion, we assign the cell the value 0 as it is no
longer in use. Also we switch OFF the corresponding bit in "rows", "cols" and "grid".
TIME COMPLEXITY- O(n3)
For every unassigned position, there are n options available.
SPACE COMPLEXITY- O(n)
The space complexity for the function is linear as we are maintaining three arrays
for storing bit manipulation results. Recursive space complexity is not taken into
account here.
We end our discussion here. If you faced any difficulties in this article, just watch
the solution video for it.
